{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Surrounded Regions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: solve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #被围绕的区域"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个 <code>m x n</code> 的矩阵 <code>board</code> ，由若干字符 <code>'X'</code> 和 <code>'O'</code> ，找到所有被 <code>'X'</code> 围绕的区域，并将这些区域里所有的 <code>'O'</code> 用 <code>'X'</code> 填充。\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg\" style=\"width: 550px; height: 237px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"X\",\"X\",\"X\",\"X\"],[\"X\",\"O\",\"O\",\"X\"],[\"X\",\"X\",\"O\",\"X\"],[\"X\",\"O\",\"X\",\"X\"]]\n",
    "<strong>输出：</strong>[[\"X\",\"X\",\"X\",\"X\"],[\"X\",\"X\",\"X\",\"X\"],[\"X\",\"X\",\"X\",\"X\"],[\"X\",\"O\",\"X\",\"X\"]]\n",
    "<strong>解释：</strong>被围绕的区间不会存在于边界上，换句话说，任何边界上的 <code>'O'</code> 都不会被填充为 <code>'X'</code>。 任何不在边界上，或不与边界上的 <code>'O'</code> 相连的 <code>'O'</code> 最终都会被填充为 <code>'X'</code>。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"X\"]]\n",
    "<strong>输出：</strong>[[\"X\"]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 200</code></li>\n",
    "\t<li><code>board[i][j]</code> 为 <code>'X'</code> 或 <code>'O'</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [surrounded-regions](https://leetcode.cn/problems/surrounded-regions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [surrounded-regions](https://leetcode.cn/problems/surrounded-regions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"X\",\"X\",\"X\",\"X\"],[\"X\",\"O\",\"O\",\"X\"],[\"X\",\"X\",\"O\",\"X\"],[\"X\",\"O\",\"X\",\"X\"]]', '[[\"X\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def solve(s, n, p):\n",
    "            @cache\n",
    "            def f(i, is_limit, is_num, cnt):\n",
    "                if i == n:\n",
    "                    return cnt\n",
    "                res = 0\n",
    "                if is_num == 0:\n",
    "                    res = f(i + 1, False, False, cnt)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    res += f(i + 1, is_limit and (d == up), True, cnt + (d == p))\n",
    "                return res\n",
    "            return f(0,True,False, 0) \n",
    "        print(solve(str(10),2,1))     \n",
    "        return solve(str(high),len(str(high)), d)  - solve(str(low - 1),len(str(low - 1)), d)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def solve(s, n, p):\n",
    "            @cache\n",
    "            def f(i, is_limit, is_num, cnt):\n",
    "                if i == n:\n",
    "                    return cnt\n",
    "                res = 0\n",
    "                if is_num == 0:\n",
    "                    res = f(i + 1, False, False, cnt)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    res += f(i + 1, is_limit and (d == up), True, cnt + (d == p))\n",
    "                return res\n",
    "            return f(0,True,False, 0) \n",
    "        print(solve(str(10),2,1))     \n",
    "        return solve(str(high),len(str(high)), d)  - solve(str(low - 1),len(str(low - 1)), d)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def solve(self, board: List[List[str]]) -> None:\n",
    "#         \"\"\"\n",
    "#         Do not return anything, modify board in-place instead.\n",
    "#         \"\"\"\n",
    "#         if not board: return\n",
    "\n",
    "#         m = len(board)\n",
    "#         n = len(board[0])\n",
    "#         stack = []\n",
    "\n",
    "#         for i in range(m):\n",
    "#             if board[i][0] == 'O':\n",
    "#                 board[i][0] = 'A'\n",
    "#                 stack.append((i,0))\n",
    "#             if board[i][n-1] == 'O':\n",
    "#                 board[i][n-1] == 'A'\n",
    "#                 stack.append((i,n-1))\n",
    "#         for j in range(n):\n",
    "#             if board[0][j] == 'O':\n",
    "#                 board[0][j] = 'A'\n",
    "#                 stack.append((0,j))\n",
    "#             if board[m-1][j] == 'O':\n",
    "#                 board[m-1][j] = 'A'\n",
    "#                 stack.append((m-1,j))\n",
    "        \n",
    "#         while stack:\n",
    "#             x, y = stack.pop()\n",
    "#             for u, v in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "#                 if 0<u<m-1 and 0<v<n-1 and board[u][v] == 'O':\n",
    "#                     stack.append((u,v))\n",
    "#                     board[u][v] = 'A'\n",
    "\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if board[i][j] == 'O':\n",
    "#                     board[i][j] = 'X'\n",
    "#                 if board[i][j] == 'A':\n",
    "#                     board[i][j] = 'O'\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        if not board:\n",
    "            return\n",
    "        \n",
    "        n, m = len(board), len(board[0])\n",
    "        que = []\n",
    "        for i in range(n):\n",
    "            if board[i][0] == \"O\":\n",
    "                que.append((i, 0))\n",
    "                board[i][0] = \"A\"\n",
    "            if board[i][m - 1] == \"O\":\n",
    "                que.append((i, m - 1))\n",
    "                board[i][m - 1] = \"A\"\n",
    "        for i in range(m):\n",
    "            if board[0][i] == \"O\":\n",
    "                que.append((0, i))\n",
    "                board[0][i] = \"A\"\n",
    "            if board[n - 1][i] == \"O\":\n",
    "                que.append((n - 1, i))\n",
    "                board[n - 1][i] = \"A\"\n",
    "        \n",
    "        while que:\n",
    "            x, y = que.pop()\n",
    "            for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 < mx < n-1 and 0 < my < m-1 and board[mx][my] == \"O\":\n",
    "                    que.append((mx, my))\n",
    "                    board[mx][my] = \"A\"\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if board[i][j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "                if board[i][j] == \"A\":\n",
    "                    board[i][j] = \"O\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if not board or not board[0]:\n",
    "            return\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            from collections import deque\n",
    "            queue = deque()\n",
    "            queue.appendleft((i, j))\n",
    "            while queue:\n",
    "                i, j = queue.pop()\n",
    "                if 0 <= i < row and 0 <= j < col and board[i][j] == \"O\":\n",
    "                    board[i][j] = \"B\"\n",
    "                    for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        queue.appendleft((i + x, j + y))\n",
    "\n",
    "        for j in range(col):\n",
    "            # 第一行\n",
    "            if board[0][j] == \"O\":\n",
    "                bfs(0, j)\n",
    "            # 最后一行\n",
    "            if board[row - 1][j] == \"O\":\n",
    "                bfs(row - 1, j)\n",
    "\n",
    "        for i in range(row):\n",
    "\n",
    "            if board[i][0] == \"O\":\n",
    "                bfs(i, 0)\n",
    "            if board[i][col - 1] == \"O\":\n",
    "                bfs(i, col - 1)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "                if board[i][j] == \"B\":\n",
    "                    board[i][j] = \"O\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        row, col = len(board), len(board[0])\n",
    "        helper = set()\n",
    "        def process(x, y):\n",
    "            if x<0 or x>=row or y<0 or y>=col: return\n",
    "            if board[x][y] != \"O\": return\n",
    "            board[x][y] = \"#\"\n",
    "            process(x+1, y)\n",
    "            process(x-1, y)\n",
    "            process(x, y+1)\n",
    "            process(x, y-1)\n",
    "\n",
    "\n",
    "        for j in range(col):\n",
    "            if board[0][j] == \"O\":\n",
    "                process(0, j)\n",
    "            if board[row-1][j] == \"O\":\n",
    "                process(row-1, j)\n",
    "        for i in range(row):\n",
    "            if board[i][0] == \"O\":\n",
    "                process(i, 0)\n",
    "            if board[i][col-1] == \"O\":\n",
    "                process(i, col-1)\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "                if board[i][j] == \"#\":\n",
    "                    board[i][j] = \"O\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        surrounded = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        for i in range(0, row):\n",
    "            for j in range(0, col):\n",
    "                if (i==0 or j==0 or i==row-1 or j==col-1) and board[i][j]=='O':\n",
    "                    if surrounded[i][j]==1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        self.dfs(i, j, surrounded, board)\n",
    "        for i in range(0, row):\n",
    "            for j in range(0, col):\n",
    "                if surrounded[i][j] == 0:\n",
    "                    board[i][j] = 'X'\n",
    "\n",
    "    def dfs(self, i, j, surrounded, board):\n",
    "        direction = [-1, 0, 1, 0, -1]\n",
    "        if i>=len(surrounded) or j>=len(surrounded[0]) or i<0 or j<0:\n",
    "            return []\n",
    "        if board[i][j] == 'O':\n",
    "            surrounded[i][j] = 1\n",
    "            for k in range(0, 4):\n",
    "                i_new = i+direction[k:k+2][0]\n",
    "                j_new = j+direction[k:k+2][1]\n",
    "                if i_new>=len(surrounded) or j_new>=len(surrounded[0]) or i_new<0 or j_new<0 or surrounded[i_new][j_new]==1:\n",
    "                    continue\n",
    "                else:\n",
    "                    self.dfs(i_new,j_new,surrounded,board)\n",
    "        return []\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if not board:\n",
    "            return\n",
    "        m, n = len(board), len(board[0])\n",
    "        uf = UF(m * n + 1)   # 给 dummy 留一个额外位置\n",
    "        dummy = m * n\n",
    "        # 将首列和末列的 O 与 dummy 连通\n",
    "        for i in range(m):\n",
    "            if board[i][0] == 'O':\n",
    "                uf.union(i * n, dummy)\n",
    "            if board[i][n - 1] == 'O':\n",
    "                uf.union(i * n + n - 1, dummy)\n",
    "        # 将首行和末行的 O 与 dummy 连通\n",
    "        for j in range(n):\n",
    "            # extend up -150\n",
    "            if board[0][j] == 'O':\n",
    "                uf.union(j, dummy)\n",
    "            if board[m - 1][j] == 'O':\n",
    "                uf.union(n * (m - 1) + j, dummy)\n",
    "        # 方向数组 d 是上下左右搜索的常用手法\n",
    "        d = [[1, 0], [0, 1], [0, -1], [-1, 0]]\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if board[i][j] == 'O':\n",
    "                    # 将此 O 与上下左右的 O 连通\n",
    "                    for k in range(4):\n",
    "                        x = i + d[k][0]\n",
    "                        y = j + d[k][1]\n",
    "                        if board[x][y] == 'O':\n",
    "                            uf.union(x * n + y, i * n + j)\n",
    "        # 所有不和 dummy 连通的 O，都要被替换\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if not uf.connected(dummy, i * n + j):\n",
    "                    board[i][j] = 'X'\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.count = 0\n",
    "        self.parent = [i for i in range(n)]\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def connected(self, p: int, q: int) -> bool:\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        return rootP == rootQ\n",
    "    def union(self, p: int, q: int):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "        self.parent[rootQ] = rootP\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 根据题目解释，边界属于一个类，和边界相连的话就是同一个类\n",
    "        \"\"\"\n",
    "        怎么存储O是一个问题，字典存储是否为边界。\n",
    "        用一个类还是不太行\n",
    "        \"\"\"\n",
    "        f = list(range(len(board) * len(board[0]) + 1))\n",
    "        def find(x):\n",
    "            # f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        def union(x, y):\n",
    "            f[find(y)] = find(x)\n",
    "\n",
    "            \n",
    "            \n",
    "        if not board or not board[0]:\n",
    "            return\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        dummy = row * col\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == \"O\":\n",
    "                    if i == 0 or i == row - 1 or j == 0 or j == col - 1:\n",
    "                        union(i * col + j, dummy)\n",
    "                    else:\n",
    "                        for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                            if board[i + x][j + y] == \"O\":\n",
    "                                union(i * col + j, (i + x) * col + (j + y))\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if find(dummy) == find(i * col + j):\n",
    "                    board[i][j] = \"O\"\n",
    "                else:\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        f = {}\n",
    "        def find(x):\n",
    "            #如果不存在x则初始化指向自身\n",
    "            f.setdefault(x,x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        def union(x,y):\n",
    "            f[find(x)] = find(y)\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "        dummy = n * m\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if board[i][j] == 'O':\n",
    "                    if i == 0 or i == n - 1 or j == 0 or j == m - 1:\n",
    "                        union(i * m + j,dummy)\n",
    "                    else:\n",
    "                        for x,y in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                            if board[i + x][j + y] == 'O':\n",
    "                                union(i * m + j,(i + x) * m + j + y)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if find(dummy) == find(i * m + j):\n",
    "                    board[i][j] = \"O\"\n",
    "                else:\n",
    "                    board[i][j] = \"X\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 根据题目解释，边界属于一个类，和边界相连的话就是同一个类\n",
    "        \"\"\"\n",
    "        怎么存储O是一个问题，字典存储是否为边界。\n",
    "        用一个类还是不太行\n",
    "        \"\"\"\n",
    "        f = {}\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        def union(x, y):\n",
    "            f[find(y)] = find(x)\n",
    "\n",
    "            \n",
    "            \n",
    "        if not board or not board[0]:\n",
    "            return\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        dummy = row * col\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == \"O\":\n",
    "                    if i == 0 or i == row - 1 or j == 0 or j == col - 1:\n",
    "                        union(i * col + j, dummy)\n",
    "                    else:\n",
    "                        for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                            if board[i + x][j + y] == \"O\":\n",
    "                                union(i * col + j, (i + x) * col + (j + y))\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if find(dummy) == find(i * col + j):\n",
    "                    board[i][j] = \"O\"\n",
    "                else:\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(i,j,filpWord,target=\"O\"):\n",
    "            if board[i][j]!=target:\n",
    "                return\n",
    "            que = []\n",
    "            que.append((i,j))\n",
    "            while que:\n",
    "                (oi,oj) = que.pop()\n",
    "                if oi<0 or oi>=len(board) or oj<0 or oj>=len(board[0]):\n",
    "                    continue\n",
    "                if board[oi][oj]==target:\n",
    "                    board[oi][oj]=filpWord\n",
    "                    que.append((oi,oj-1))   \n",
    "                    que.append((oi,oj+1))  \n",
    "                    que.append((oi-1,oj))   \n",
    "                    que.append((oi+1,oj))   \n",
    "        def true_dfs(i,j,filpWord,target=\"O\"):\n",
    "            if i<0 or i>=len(board) or j<0 or j>=len(board[0]):\n",
    "                return\n",
    "            if board[i][j]==target:\n",
    "                board[i][j]=filpWord\n",
    "                dfs(i,j-1,filpWord)\n",
    "                dfs(i-1,j,filpWord)\n",
    "                dfs(i+1,j,filpWord)\n",
    "                dfs(i,j+1,filpWord)\n",
    "        i_len = len(board)\n",
    "        j_len = len(board[0])\n",
    "        for i in range(i_len):\n",
    "            if board[i][0]=='O':\n",
    "                dfs(i,0,'A')\n",
    "            if board[i][j_len-1]=='O':\n",
    "                dfs(i,j_len-1,'A')\n",
    "        for j in range(j_len):\n",
    "            if board[0][j]=='O':\n",
    "                dfs(0,j,'A')\n",
    "            if board[i_len-1][j]=='O':\n",
    "                dfs(i_len-1,j,'A')\n",
    "        print(board)\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if board[i][j]=='O':\n",
    "                    dfs(i,j,'X')\n",
    "        print(board)\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if board[i][j]=='A':\n",
    "                    board[i][j]='O'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        directs = [[-1, 0], [0, -1], [1, 0], [0, 1]]\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\" and visit[i][j] == 0:\n",
    "                    q = [(i, j)]\n",
    "                    tmp = [(i, j)]\n",
    "                    visit[i][j] = 1\n",
    "                    if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        flag = 0\n",
    "                    while q:\n",
    "                        ind = q.pop()\n",
    "                        for a in directs:\n",
    "                            row, col = ind[0] + a[0], ind[1] + a[1]\n",
    "                            if 0 <= row < m and 0 <= col < n and board[row][col] == \"O\" and visit[row][col] == 0:\n",
    "                                visit[row][col] = 1\n",
    "                                q.append((row, col))\n",
    "                                tmp.append((row, col))\n",
    "                                if row == 0 or row == m - 1 or col == 0 or col == n - 1:\n",
    "                                    flag = 1\n",
    "                    if flag == 0:\n",
    "                        while tmp:\n",
    "                            row, col = tmp.pop()\n",
    "                            board[row][col] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        size1, size2 = len(board), len(board[0])\n",
    "\n",
    "        for i1 in range(size1):\n",
    "            for i2 in range(size2):\n",
    "                if board[i1][i2] == \"0\":\n",
    "                    continue\n",
    "\n",
    "                land = {(i1, i2)}\n",
    "                is_boundary = False\n",
    "                pos_list = collections.deque([(i1, i2)])\n",
    "                while pos_list:\n",
    "                    (i3, i4) = pos_list.popleft()\n",
    "                    if i3 + 1 < size1 and board[i3 + 1][i4] == \"O\" and (i3 + 1, i4) not in land:\n",
    "                        land.add((i3 + 1, i4))\n",
    "                        pos_list.append((i3 + 1, i4))\n",
    "                    elif i3 + 1 >= size1:\n",
    "                        is_boundary = True\n",
    "\n",
    "                    if i4 + 1 < size2 and board[i3][i4 + 1] == \"O\" and (i3, i4 + 1) not in land:\n",
    "                        land.add((i3, i4 + 1))\n",
    "                        pos_list.append((i3, i4 + 1))\n",
    "                    elif i4 + 1 >= size2:\n",
    "                        is_boundary = True\n",
    "\n",
    "                    if i3 - 1 >= 0 and board[i3 - 1][i4] == \"O\" and (i3 - 1, i4) not in land:\n",
    "                        land.add((i3 - 1, i4))\n",
    "                        pos_list.append((i3 - 1, i4))\n",
    "                    elif i3 - 1 < 0:\n",
    "                        is_boundary = True\n",
    "\n",
    "                    if i4 - 1 >= 0 and board[i3][i4 - 1] == \"O\" and (i3, i4 - 1) not in land:\n",
    "                        land.add((i3, i4 - 1))\n",
    "                        pos_list.append((i3, i4 - 1))\n",
    "                    elif i4 - 1 < 0:\n",
    "                        is_boundary = True\n",
    "\n",
    "                if not is_boundary:\n",
    "                    for point in land:\n",
    "                        board[point[0]][point[1]] = \"X\"\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def gen_wei(i,j,board,wei):\n",
    "\n",
    "            if i == 0 or j == 0 or i == len(board)-1 or j == len(board[i])-1:\n",
    "                if board[i][j] == 'X':\n",
    "                    return \n",
    "                else:\n",
    "                    wei[i][j] = 1\n",
    "                    return\n",
    "            elif wei[i-1][j] == 1 or wei[i+1][j] == 1 or wei[i][j-1] == 1 or wei[i][j+1] == 1:\n",
    "                wei[i][j] = 1\n",
    "                return\n",
    "            else:\n",
    "                flag = False\n",
    "                li = [(i,j)]\n",
    "                all_node = set()\n",
    "                while len(li) > 0:\n",
    "                    temp = li.pop(0)\n",
    "                    all_node.add(temp)\n",
    "                    if wei[temp[0]][temp[1]] == 1:\n",
    "                        flag = True\n",
    "\n",
    "                    if temp[0]-1 >= 0 and board[temp[0]-1][temp[1]] != 'X' and (temp[0]-1,temp[1]) not in all_node:\n",
    "                        li.append((temp[0]-1,temp[1]))\n",
    "                        all_node.add((temp[0]-1,temp[1]))\n",
    "                    if temp[0]+1 < len(board) and board[temp[0]+1][temp[1]] != 'X' and (temp[0]+1,temp[1]) not in all_node:\n",
    "                        li.append((temp[0]+1,temp[1]))\n",
    "                        all_node.add((temp[0]+1,temp[1]))\n",
    "                    if temp[1]-1 >= 0 and board[temp[0]][temp[1]-1] != 'X' and (temp[0],temp[1]-1) not in all_node:\n",
    "                        li.append((temp[0],temp[1]-1))\n",
    "                        all_node.add((temp[0],temp[1]-1))\n",
    "                    if temp[1]+1 < len(board[temp[0]]) and board[temp[0]][temp[1]+1] != 'X' and (temp[0],temp[1]+1) not in all_node:\n",
    "                        li.append((temp[0],temp[1]+1))\n",
    "                        all_node.add((temp[0],temp[1]+1))\n",
    "                \n",
    "                print(all_node)\n",
    "                if flag == True:\n",
    "                    for s in all_node:\n",
    "                        wei[s[0]][s[1]]=1\n",
    "                    return\n",
    "                else:\n",
    "                    for s in all_node:\n",
    "                        wei[s[0]][s[1]]=2\n",
    "                    return\n",
    "\n",
    "        m = len(board)\n",
    "        if m <= 0: return\n",
    "        n = len(board[0])\n",
    "        if n <= 0: return\n",
    "        \n",
    "        wei = []\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            wei.append([])\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                if board[i][j] == 'X':\n",
    "                    wei[i].append(3)\n",
    "                else:\n",
    "                    wei[i].append(0)\n",
    "                j+=1\n",
    "            i+=1\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if board[0][i] == 'O':\n",
    "                wei[0][i] = 1\n",
    "            if board[m-1][i] == 'O':\n",
    "                wei[m-1][i] = 1\n",
    "            i+=1\n",
    "        \n",
    "        i = 0\n",
    "        while i < m:\n",
    "            if board[i][0] == 'O':\n",
    "                wei[i][0] = 1\n",
    "            if board[i][n-1] == 'O':\n",
    "                wei[i][n-1] = 1\n",
    "            i+=1\n",
    "\n",
    "        # print(wei)\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                if board[i][j] == 'O' and wei[i][j] == 0:\n",
    "                    gen_wei(i,j,board,wei)\n",
    "                    print(i,j,wei)\n",
    "                j+=1\n",
    "            i+=1\n",
    "\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                if wei[i][j] == 2:\n",
    "                    board[i][j] = 'X'\n",
    "                j+=1\n",
    "            i+=1\n",
    "\n",
    "        # i = 0\n",
    "        # while i < m:\n",
    "        #     j = 0\n",
    "        #     while j < n:\n",
    "        #         if wei[i][j] == 2:\n",
    "        #             board[i][j] = 'X'\n",
    "        #         j+=1\n",
    "        #     i+=1\n",
    "        # weigh = []\n",
    "        # high = []\n",
    "        # i = 0\n",
    "        # while i < len(board):           \n",
    "        #     j=0\n",
    "        #     left = -1\n",
    "        #     while j < len(board[i]):\n",
    "        #         if board[i][j] == 'X':\n",
    "        #             left = j\n",
    "        #             break\n",
    "        #         j+=1\n",
    "            \n",
    "        #     j=len(board[i])-1\n",
    "        #     right = -1\n",
    "        #     while j>=0:\n",
    "        #         if board[i][j] == 'X':\n",
    "        #             right = j\n",
    "        #             break\n",
    "        #         j-=1\n",
    "\n",
    "        #     if left!=-1 and right!=-1 and left != right:\n",
    "        #         k = left+1\n",
    "        #         while k < right:\n",
    "        #             if board[i][k] == \"O\":\n",
    "        #                 tempboard[i][k] = \"L\"\n",
    "        #             k+=1\n",
    "        #     i+=1\n",
    "\n",
    "        # # print(tempboard)\n",
    "        # i = 0\n",
    "        # while i < n:\n",
    "        #     j = 0\n",
    "        #     up = -1\n",
    "        #     while j < m:\n",
    "        #         if board[j][i] == 'X':\n",
    "        #             up = j\n",
    "        #             break\n",
    "        #         j+=1\n",
    "            \n",
    "        #     down = -1\n",
    "        #     j = m-1\n",
    "        #     while j>=0:\n",
    "        #         if board[j][i] == 'X':\n",
    "        #             down = j\n",
    "        #             break\n",
    "        #         j-=1\n",
    "\n",
    "        #     if up != -1 and down != -1 and up != down:\n",
    "        #         # print(i,j,up,down)\n",
    "        #         k = up+1\n",
    "        #         while k < down:\n",
    "        #             if tempboard[k][i] == 'L':\n",
    "        #                 board[k][i] = 'X'\n",
    "        #             k+=1\n",
    "        #     i+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = {}\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if board[x][y] == 'X':\n",
    "                    continue\n",
    "                if (x, y) in visited:\n",
    "                    continue\n",
    "                flag = True if x != 0 and y != 0 and x != m-1 and y != n-1 else False\n",
    "                pos = []\n",
    "                q = [(x, y)]\n",
    "                while q:\n",
    "                    next_q = []\n",
    "                    for i, j in q:\n",
    "                        if (i, j) in visited:\n",
    "                            continue\n",
    "                        visited[(i, j)] = 1\n",
    "                        pos.append((i, j))\n",
    "                        for ii, jj in [(i, j-1), (i-1, j), (i, j+1), (i+1, j)]:\n",
    "                            if ii < 0 or jj < 0 or ii >= m or jj >= n:\n",
    "                                continue\n",
    "                            if board[ii][jj] == 'X':\n",
    "                                continue\n",
    "                            if ii == 0 or jj == 0 or ii == m-1 or jj == n-1:\n",
    "                                flag = False\n",
    "                            next_q.append((ii, jj))\n",
    "                    q = next_q\n",
    "                if flag:\n",
    "                    for i, j in pos:\n",
    "                        board[i][j] = 'X'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"16->\"\"\"\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        x_set = set()\n",
    "        o_set = set()\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == \"O\":\n",
    "                    o_set.add((i, j))\n",
    "                else:\n",
    "                    x_set.add((i, j))\n",
    "\n",
    "        while o_set:\n",
    "            _v = o_set.pop()\n",
    "\n",
    "            que = deque([_v])\n",
    "            o_island = set([_v])\n",
    "\n",
    "            while que:\n",
    "                i, j = que.popleft()\n",
    "                surround = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "                for offset_i, offset_j in surround:\n",
    "                    _i, _j = i + offset_i, j + offset_j\n",
    "                    if (_i, _j) in o_set:\n",
    "                        o_set.remove((_i, _j))\n",
    "                        que.append((_i, _j))\n",
    "                        o_island.add((_i, _j))\n",
    "\n",
    "            all_in = True\n",
    "            for i, j in o_island:\n",
    "                surround = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "                for offset_i, offset_j in surround:\n",
    "                    _i, _j = i + offset_i, j + offset_j\n",
    "                    if (_i, _j) in o_island or (_i, _j) in x_set:\n",
    "                        pass\n",
    "                    else:\n",
    "                        all_in = False\n",
    "                        break\n",
    "\n",
    "            if all_in:\n",
    "                for i, j in o_island:\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        li0 = [] \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\":\n",
    "                    li0.append((i, j))\n",
    "        print(li0)\n",
    "        while li0:\n",
    "            (r, c) = li0[0]\n",
    "            queue = collections.deque([(r, c)])\n",
    "            ans = {(r, c)}\n",
    "            Flag = True\n",
    "            while queue:\n",
    "                x, y = queue.popleft()\n",
    "                if x in [0, m-1] or y in [0, n-1]:\n",
    "                    Flag = False\n",
    "                for xx, yy in [(x, y -1), (x, y + 1), (x + 1, y), (x - 1, y)]:\n",
    "                    if 0 <= xx < m and 0 <= yy < n and board[xx][yy] == \"O\" and (xx, yy) not in ans:\n",
    "                        queue.append((xx, yy))\n",
    "                        ans.add((xx, yy))\n",
    "            for i, j in ans:\n",
    "                if Flag:\n",
    "                    board[i][j] = \"X\"\n",
    "                li0.remove((i, j))\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.DIRECTIONS = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        rows, cols = len(board), len(board[0])\n",
    "        visited = set()\n",
    "        res = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if board[i][j] == \"X\" or (i, j) in visited:\n",
    "                    continue\n",
    "                res.extend(self.bfs(i, j, board, visited))\n",
    "                # print(res)\n",
    "        for i, j in res:  # 不能在中间改矩阵！！\n",
    "            board[i][j] = \"X\"\n",
    "\n",
    "    def bfs(self, i, j, board, visited):\n",
    "        queue = collections.deque([(i, j)])\n",
    "        visited.add((i, j))\n",
    "        res = [(i, j)]\n",
    "        not_change = False\n",
    "        not_change = self.is_edge(i, j, board, not_change)\n",
    "        while queue:\n",
    "            node_i, node_j = queue.popleft()\n",
    "            for i, j in self.DIRECTIONS:\n",
    "                neighbor_i, neighbor_j = node_i+i, node_j+j\n",
    "                if not self.is_valid(neighbor_i, neighbor_j, board, visited):\n",
    "                    continue\n",
    "                # 如果不是O或者越界则跳过\n",
    "                not_change = self.is_edge(neighbor_i, neighbor_j, board, not_change)\n",
    "                queue.append((neighbor_i, neighbor_j))\n",
    "                visited.add((neighbor_i, neighbor_j))\n",
    "                res.append((neighbor_i, neighbor_j))\n",
    "        if not_change:\n",
    "            return []\n",
    "        return res\n",
    "\n",
    "    def is_valid(self, i, j, board, visited):\n",
    "        if i >= len(board) or j >= len(board[0]) or i < 0 or j < 0:\n",
    "            return False\n",
    "        if board[i][j] == \"X\" or (i, j) in visited:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def is_edge(self, i, j, board, not_change):\n",
    "        if i == 0 or j == 0 or i == len(board)-1 or j == len(board[0])-1:\n",
    "            return True\n",
    "        return not_change\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        direction = [(1, 0), (-1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        def is_valid(x, y):\n",
    "            return 0 <= x <= m-1 and 0 <= y <= n-1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\" and not visited[i][j]:\n",
    "                    # print(i, j)\n",
    "                    is_inside = True\n",
    "                    queue = [(i, j)]\n",
    "                    record = [(i, j)]\n",
    "                    while queue:\n",
    "                        x, y = queue.pop()\n",
    "                        # print('____')\n",
    "                        # print(x, y)\n",
    "                        visited[x][y] = True\n",
    "                        for d in direction:\n",
    "                            nx, ny = x + d[0], y + d[1]\n",
    "                            if is_valid(nx, ny):\n",
    "                                # print(nx, ny)\n",
    "                                if board[nx][ny] == \"O\" and not visited[nx][ny]:\n",
    "                                    queue.append((nx, ny))\n",
    "                                    record.append((nx, ny))\n",
    "                                    # print(nx, ny)\n",
    "                            else:\n",
    "                                is_inside = False\n",
    "                    if is_inside:\n",
    "                        for (x, y) in record:\n",
    "                            board[x][y] = \"X\"\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        pa = {(-1, -1): (-1, -1)}\n",
    "        sz = {(-1, -1): 1}\n",
    "\n",
    "        def find(x):\n",
    "            while pa[x] != x: x = pa[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            # print(pa, sz, x, y)\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry: return\n",
    "            if sz[rx] < sz[ry]:\n",
    "                pa[rx] = pa[ry]\n",
    "                sz[ry] += sz[rx]\n",
    "            else:\n",
    "                pa[ry] = pa[rx]\n",
    "                sz[rx] += sz[ry]\n",
    "            \n",
    "\n",
    "        def shori(i, j):\n",
    "            for ii, jj in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)]:\n",
    "                if ii in range(m) and jj in range(n) and board[ii][jj] == 'O':\n",
    "                    union((i, j), (ii, jj))\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    pa[(i, j)] = (i, j)\n",
    "                    sz[(i, j)] = 1\n",
    "\n",
    "        for i, j in pa:\n",
    "            if board[i][j] == 'O':\n",
    "                shori(i, j)\n",
    "            if i == 0 or j == 0 or i == m-1 or j == n-1:\n",
    "                union((i, j), (-1, -1))\n",
    "\n",
    "        # print(pa)\n",
    "\n",
    "        for i, j in pa:\n",
    "            if i >= 0 and find((i, j)) != find((-1, -1)):\n",
    "                board[i][j] = \"X\"\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        opoints = set()\n",
    "        limitpoints = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\":\n",
    "                    opoints.add((i,j))\n",
    "                    if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                        limitpoints.add((i,j))\n",
    "        \n",
    "        for i,j in opoints:\n",
    "            if board[i][j] == \"O\" and (i,j) not in limitpoints:\n",
    "                queue = deque([(i, j)])\n",
    "                mark = set([(i, j)])\n",
    "                flag = False\n",
    "                while len(queue):\n",
    "                    queuei, queuej = queue.popleft()\n",
    "                    for posi, posj in [(1,0), (-1,0), (0,1),(0,-1)]:\n",
    "                        newi, newj = queuei+posi, queuej+posj\n",
    "                        if 0 <= newi < m and 0 <= newj < n and (newi, newj) in opoints and (newi, newj) not in mark:\n",
    "                            mark.add((newi, newj))\n",
    "                            queue.append((newi, newj))\n",
    "                            if (newi, newj) in limitpoints:\n",
    "                                flag = True\n",
    "                \n",
    "                \n",
    "                for i,j in mark:\n",
    "                    if not flag:\n",
    "                        board[i][j] = \"X\"\n",
    "                    else:\n",
    "                        limitpoints.add((i,j))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        n_rows = len(board)\n",
    "        n_cols = len(board[0])\n",
    "        visited = [[0] * n_cols for _ in range(n_rows)]\n",
    "        o_island = []\n",
    "        for i in range(n_rows):\n",
    "            for j in range(n_cols):\n",
    "                if board[i][j] == 'X' or visited[i][j] == 1:\n",
    "                    pass\n",
    "                else:\n",
    "                    stack = [[i,j]]\n",
    "                    island = [[i,j]]\n",
    "                    while stack:\n",
    "                        tmp = stack.pop()\n",
    "                        r = tmp[0]\n",
    "                        c = tmp[1]\n",
    "                        visited[r][c] = 1\n",
    "                        if r - 1>=0 and board[r-1][c] == 'O' and visited[r-1][c] == 0:\n",
    "                            stack.append([r-1,c])\n",
    "                            island.append([r-1,c])\n",
    "                        if r + 1<n_rows and board[r+1][c] == 'O' and visited[r+1][c] == 0:\n",
    "                            stack.append([r+1,c])\n",
    "                            island.append([r+1,c])\n",
    "                        if c - 1>=0 and board[r][c-1] == 'O' and visited[r][c-1] == 0:\n",
    "                            stack.append([r,c-1])\n",
    "                            island.append([r,c-1])\n",
    "                        if c + 1<n_cols and board[r][c+1] == 'O' and visited[r][c+1] == 0:\n",
    "                            stack.append([r,c+1])\n",
    "                            island.append([r,c+1])\n",
    "                    o_island.append(island)\n",
    "        island_flag = [0] * len(o_island)\n",
    "        for i, island in enumerate(o_island):\n",
    "            for r, c in island:\n",
    "                if r==0 or r==n_rows-1 or c==0 or c==n_cols-1:\n",
    "                    island_flag[i] = 1\n",
    "                    break\n",
    "        for i, flag in enumerate(island_flag):\n",
    "            if flag == 0:\n",
    "                for r, c in o_island[i]:\n",
    "                    board[r][c] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 'X' or (i,j) in seen:\n",
    "                    continue\n",
    "                # DFS\n",
    "                st = []\n",
    "                st.append((i,j))\n",
    "                captured = True\n",
    "                island = []\n",
    "                while st:\n",
    "                    loc = st.pop()\n",
    "                    if loc in seen:\n",
    "                        continue\n",
    "                    seen.add(loc)\n",
    "                    island.append(loc)\n",
    "\n",
    "                    if loc[0] == 0 or loc[0] == len(board)-1 or loc[1] == 0 or loc[1] == len(board[0])-1:\n",
    "                        captured = False\n",
    "\n",
    "                    if loc[0] > 0 and board[loc[0]-1][loc[1]] == 'O':\n",
    "                        st.append((loc[0]-1,loc[1]))\n",
    "                    if loc[1] > 0 and board[loc[0]][loc[1]-1] == 'O':\n",
    "                        st.append((loc[0],loc[1]-1))\n",
    "                    if loc[0] < len(board)-1 and board[loc[0]+1][loc[1]] == 'O':\n",
    "                        st.append((loc[0]+1,loc[1]))\n",
    "                    if loc[1] < len(board[0])-1 and board[loc[0]][loc[1]+1] == 'O':\n",
    "                        st.append((loc[0],loc[1]+1))\n",
    "                \n",
    "                if captured:\n",
    "                    for loc in island:\n",
    "                        board[loc[0]][loc[1]] = 'X'\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        height = len(board)\n",
    "        width = len(board[0])\n",
    "\n",
    "        edge_area = set()\n",
    "\n",
    "        for i, row in enumerate(board):\n",
    "            for j, e in enumerate(row):\n",
    "                if e == \"X\":\n",
    "                    continue\n",
    "                if (i, j) in edge_area:\n",
    "                    continue\n",
    "\n",
    "                s = set()\n",
    "                q = [(i, j)]\n",
    "                while q:\n",
    "                    x, y = q.pop()\n",
    "                    if not (0 <= x < height and 0 <= y < width):\n",
    "                        continue\n",
    "\n",
    "                    if board[x][y] == \"X\":\n",
    "                        continue\n",
    "\n",
    "                    # reach edge\n",
    "                    if x == 0 or x == height - 1 or y == 0 or y == width - 1:\n",
    "                        for p in s:\n",
    "                            edge_area.add(p)\n",
    "                        break\n",
    "\n",
    "                    if (x, y) in s:\n",
    "                        continue\n",
    "                    s.add((x, y))\n",
    "\n",
    "                    q.append((x - 1, y))\n",
    "                    q.append((x + 1, y))\n",
    "                    q.append((x, y - 1))\n",
    "                    q.append((x, y + 1))\n",
    "                else:\n",
    "                    for x, y in s:\n",
    "                        board[x][y] = \"X\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        will_be_change_list = []\n",
    "        visited = set()\n",
    "        def judge_area(row, col):\n",
    "            directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "            stack = [(row, col)]\n",
    "            area = [(row, col)]\n",
    "            flag = False            \n",
    "            while stack:\n",
    "                pos = stack.pop()\n",
    "                visited.add(pos)\n",
    "                for direction in directions:\n",
    "                    row = pos[0]+direction[0]\n",
    "                    col = pos[1]+direction[1]\n",
    "                    if 0 <= row < m and 0 <= col < n and board[row][col] == \"O\":\n",
    "                        if row == 0 or col == 0 or row == m-1 or col == n-1:\n",
    "                            flag = True\n",
    "                        else:\n",
    "                            if (row,col) not in visited:\n",
    "                                stack.append((row, col))\n",
    "                                area.append((row,col))\n",
    "            if flag:\n",
    "                return []\n",
    "            else:\n",
    "                return area\n",
    "\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                cell = board[i][j]\n",
    "                if cell == \"O\" and (i,j) not in visited:\n",
    "                    area = judge_area(i, j)\n",
    "                    #if area: print(area)\n",
    "                    will_be_change_list += area\n",
    "        if will_be_change_list:\n",
    "            for pos in will_be_change_list:\n",
    "                board[pos[0]][pos[1]] = \"X\"\n",
    "        \n",
    "        return board\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def check_is_edg(row, col):\n",
    "            if 0 < row < m - 1 and 0 < col < n - 1:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        def bfs(vertex):\n",
    "            queue = list()\n",
    "            queue.append(vertex)\n",
    "            vertex_list = list()\n",
    "            visit = copy.deepcopy(board)\n",
    "            while queue:\n",
    "                pop_len = len(queue)\n",
    "                for x in range(pop_len):\n",
    "                    v = queue.pop(0)\n",
    "                    row = v[0]\n",
    "                    col = v[1]\n",
    "                    vertex_list.append(v)\n",
    "                    if visit[row][col] == 'O' and check_is_edg(row, col):\n",
    "                        return\n",
    "                    if visit[row][col] == 'X':\n",
    "                        continue\n",
    "                    visit[row][col] = 'X'\n",
    "                    queue += [[row + 1, col], [row - 1, col], [row, col + 1], [row, col - 1]]\n",
    "            for tmp in vertex_list:\n",
    "                board[tmp[0]][tmp[1]] = 'X'\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                if board[i][j] == 'O':\n",
    "                    bfs([i, j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        ZERO = 'O'\n",
    "        def getKey(ii, jj):\n",
    "            return str(ii) + '-' + str(jj)\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        dt = collections.defaultdict(list)\n",
    "        helpers = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == ZERO:\n",
    "                    if i > 0 and board[i-1][j] == ZERO:\n",
    "                        k1, k2 = getKey(i,j), getKey(i-1, j)\n",
    "                        dt[k1].append(k2)\n",
    "                        dt[k2].append(k1)\n",
    "                    if j > 0 and board[i][j-1] == ZERO:\n",
    "                        k1, k2 = getKey(i,j), getKey(i, j-1)\n",
    "                        dt[k1].append(k2)\n",
    "                        dt[k2].append(k1)\n",
    "                    if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                        helpers.add(getKey(i,j))\n",
    "        \n",
    "        dq = collections.deque(helpers)\n",
    "        visited = set()\n",
    "        while len(dq) > 0:\n",
    "            cur = dq.popleft()\n",
    "            visited.add(cur)\n",
    "            vv = dt[cur]\n",
    "            for v in vv:\n",
    "                if v not in visited:\n",
    "                    dq.append(v)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == ZERO:\n",
    "                    if getKey(i, j) not in visited:\n",
    "                        board[i][j] = 'X'\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        values = []\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                values.append((i,j))\n",
    "        dummy_node= (m,n)\n",
    "        values.append(dummy_node)\n",
    "        union_set = UnionFindSet(values)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\":\n",
    "                    if i == 0 or i ==  m-1 or j ==0 or j == n-1:\n",
    "                        union_set.union((i,j), dummy_node)\n",
    "                        pass\n",
    "                    else:\n",
    "                        if i > 0 and board[i-1][j] == \"O\":\n",
    "                            union_set.union((i,j), (i-1, j))\n",
    "                        if i < m -1 and board[i+1][j] == \"O\":\n",
    "                            union_set.union((i,j), (i+1, j))\n",
    "                        if j > 0 and board[i][j-1] == \"O\":\n",
    "                            union_set.union((i,j), (i, j-1))\n",
    "                        if j < n-1 and board[i][j+1] ==\"O\":\n",
    "                            union_set.union((i,j), (i, j+1))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if union_set.is_same_set((i,j), dummy_node):\n",
    "                    board[i][j] = \"O\"\n",
    "                else:\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "\n",
    "\n",
    "class Element:\n",
    "\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "\n",
    "class UnionFindSet:\n",
    "\n",
    "    def __init__(self, values):\n",
    "        self.element_map = {}\n",
    "        self.father_map = {}\n",
    "        self.size_map = {}\n",
    "\n",
    "        for value in values:\n",
    "            ele = Element(value)\n",
    "            self.element_map[value] = ele\n",
    "            self.father_map[ele] = ele\n",
    "            self.size_map[ele] = 1\n",
    "        print(f'hhh is {self.element_map.get((0,0)).value}')\n",
    "        print(f'jjj {self.father_map.get(self.element_map.get((0,0)))}')\n",
    "\n",
    "    def find_father(self, ele):\n",
    "        stack = []\n",
    "        print()\n",
    "        while ele != self.father_map.get(ele):\n",
    "            stack.append(ele)\n",
    "            ele = self.father_map.get(ele)\n",
    "            print(f'ele is {ele}')\n",
    "        while stack:\n",
    "            self.father_map[stack.pop()] = ele\n",
    "        return ele \n",
    "\n",
    "    def union(self, a, b):\n",
    "        a_father = self.find_father(self.element_map.get(a))\n",
    "        b_father = self.find_father(self.element_map.get(b))\n",
    "        if a_father != b_father:\n",
    "            big = a_father if self.size_map[a_father]> self.size_map[b_father] else b_father\n",
    "            small = a_father if self.size_map[a_father] <= self.size_map[b_father] else b_father\n",
    "            self.father_map[small] = big\n",
    "            self.size_map[big] = self.size_map[small] + self.size_map[big]\n",
    "            self.size_map.pop(small)\n",
    "\n",
    "    def is_same_set(self, a, b):\n",
    "        if self.element_map.get(a) and self.element_map.get(b):\n",
    "            return self.find_father(self.element_map.get(a)) == self.find_father(self.find_father(self.element_map.get(b)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def solve(self, board):\n",
    "    if not board:return []    \n",
    "    size_x = len(board)\n",
    "    size_y = len(board[0])\n",
    "    virgin_zone = {(x,y):(x,y) for x in range(size_x) for y in range(size_y)}\n",
    "    found_block = {(x,y):[(x,y)] for x in range(size_x) for y in range(size_y)}\n",
    "    for x,y in virgin_zone:\n",
    "      kind = board[x][y]\n",
    "      for m,n in [(x+1,y),(x,y+1)]:\n",
    "        if m<0 or n<0 or m>=size_x or n>=size_y:continue\n",
    "        if board[m][n]==kind:\n",
    "          old_block = virgin_zone[(m,n)]\n",
    "          new_block = virgin_zone[(x,y)]\n",
    "          if old_block!=new_block:\n",
    "            while found_block[old_block]:\n",
    "              p, q = found_block[old_block].pop()\n",
    "              virgin_zone[(p,q)] = new_block\n",
    "              found_block[new_block].append((p,q))\n",
    "    for block in found_block.values():\n",
    "      if not block:continue\n",
    "      #print(block)\n",
    "      x, y = block[0]\n",
    "      if board[x][y]=='O' and len([(m,n) for m,n in block if m==0 or n==0 or m+1==size_x or n+1==size_y])==0:\n",
    "        for x,y in block:board[x][y] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        import numpy as np\n",
    "        def inArea(i,j,rows,cols):\n",
    "            if i>=0 and i<rows and j>=0 and j<cols:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        directions = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        def bfs(i,j,rows,cols,board,visited):\n",
    "            queue = collections.deque()\n",
    "            queue.append([i,j])\n",
    "            visited[i][j] = 1\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for d in directions:\n",
    "                    newx = cur[0]+d[0]\n",
    "                    newy = cur[1]+d[1]\n",
    "                    if inArea(newx,newy,rows,cols) and board[newx][newy] == 'O' and visited[newx][newy] == 0:\n",
    "                        queue.append([newx,newy])\n",
    "                        visited[newx][newy] = 1\n",
    "        rows = len(board)\n",
    "        cols = len(board[0])\n",
    "        res = 0\n",
    "        visited = np.zeros((rows,cols))\n",
    "        for i in range(rows):\n",
    "            if board[i][0] == 'O' and visited[i][0] == 0:\n",
    "                bfs(i,0,rows,cols,board,visited)\n",
    "            if board[i][cols-1] == 'O' and visited[i][cols-1] == 0:\n",
    "                bfs(i,cols-1,rows,cols,board,visited)\n",
    "        for j in range(cols):\n",
    "            if board[0][j] == 'O' and visited[0][j] == 0:\n",
    "                bfs(0,j,rows,cols,board,visited)\n",
    "            if board[rows-1][j] == 'O' and visited[rows-1][j] == 0:\n",
    "                bfs(rows-1,j,rows,cols,board,visited)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if board[i][j] == 'O' and visited[i][j] == 0:\n",
    "                    board[i][j] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if not board or not board[0]:\n",
    "            return\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            board[i][j] = 'B'\n",
    "            for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]:\n",
    "                if i+d[0] < 1 or i+d[0] >= m-1 or j+d[1] < 1 or j+d[1] >= n-1:\n",
    "                    continue\n",
    "                temp = board[i+d[0]][j+d[1]]\n",
    "                if temp == 'O':\n",
    "                    dfs(i+d[0], j+d[1])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if board[0][i] == 'O':\n",
    "                dfs(0, i)\n",
    "            if board[m-1][i] == 'O':\n",
    "                dfs(m-1, i)\n",
    "        for j in range(1, m-1):\n",
    "            if board[j][0] == 'O':\n",
    "                dfs(j, 0)\n",
    "            if board[j][n-1] == 'O':\n",
    "                dfs(j, n-1)    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    board[i][j] = 'X'\n",
    "                if board[i][j] == 'B':\n",
    "                    board[i][j] = 'O'\n",
    "        return \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        to = [[] for _ in range(m * n)]\n",
    "\n",
    "        dx = [1, 0, 0, -1]\n",
    "        dy = [0, 1, -1, 0]\n",
    "\n",
    "        zero_border = []\n",
    "\n",
    "        board_map = {}\n",
    "\n",
    "        used = [False for _ in range(m * n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i == 0 or j == 0 or i == m - 1 or j == n - 1) and (\n",
    "                    board[i][j] == \"O\"\n",
    "                ):\n",
    "                    zero_border.append(n * i + j)\n",
    "\n",
    "                board_map[n * i + j] = (i, j)\n",
    "\n",
    "                for d in range(4):\n",
    "                    nx = i + dx[d]\n",
    "                    ny = j + dy[d]\n",
    "\n",
    "                    if nx < 0 or ny < 0 or nx >= m or ny >= n:\n",
    "                        continue\n",
    "\n",
    "                    if board[nx][ny] == board[i][j]:\n",
    "                        to[n * nx + ny].append(n * i + j)\n",
    "\n",
    "        print(zero_border)\n",
    "        print(to)\n",
    "        for one_zero_border in zero_border:\n",
    "            queue = []\n",
    "            used[one_zero_border] = True\n",
    "            queue.append(one_zero_border)\n",
    "\n",
    "            while len(queue) != 0:\n",
    "                first = queue.pop(0)\n",
    "\n",
    "                for can_to in to[first]:\n",
    "                    if used[can_to]:\n",
    "                        continue\n",
    "\n",
    "                    used[can_to] = True\n",
    "                    queue.append(can_to)\n",
    "\n",
    "        print(used)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if used[n * i + j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "        print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.select_move = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def solve(self, board: list[list[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 用字典保存每个顶点之间的边\n",
    "        edge = collections.defaultdict(list)\n",
    "        # 用唯一id映射矩阵中的每个顶点的，并标记是否被访问过，是否为x、o，如果为o是否临water\n",
    "        id_visited = {}\n",
    "        m, n = len(board), len(board[0])\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                cur_id = self.get_id(x, y, n)\n",
    "                id_visited[cur_id] = [board[y][x], x, y, \"white\", \"island\"]\n",
    "                cur_nbr_list = self.get_legal_move(x, y, n, m)\n",
    "                for nbr in cur_nbr_list:\n",
    "                    nbr_id = self.get_id(*nbr, n)\n",
    "                    edge[cur_id].append(nbr_id)\n",
    "                if len(cur_nbr_list) != 4:\n",
    "                    id_visited[cur_id][-1] = \"water\"\n",
    "        self.bfs(id_visited, board, edge)\n",
    "\n",
    "    def bfs(self, id_map: dict, board: list, edge: dict):\n",
    "        q = queue.Queue()\n",
    "        for k, v in id_map.items():\n",
    "            if v[0] == \"O\" and v[3] == \"white\":\n",
    "                cur_list = []\n",
    "                not_close_water = True\n",
    "                q.put(k)\n",
    "                while not q.empty():\n",
    "                    cur_id = q.get()\n",
    "                    if id_map[cur_id][-1] == \"water\":\n",
    "                        not_close_water = False\n",
    "                    id_map[cur_id][3] = \"black\"\n",
    "                    cur_list.append(cur_id)\n",
    "                    for nbr in edge.get(cur_id, []):\n",
    "                        if id_map[nbr][0] == \"O\" and id_map[nbr][3] == \"white\":\n",
    "                            id_map[nbr][3] = \"gray\"\n",
    "                            cur_list.append(nbr)\n",
    "                            q.put(nbr)\n",
    "                if not_close_water:\n",
    "                    for bad in cur_list:\n",
    "                        bad_info = id_map[bad]\n",
    "                        board[bad_info[2]][bad_info[1]] = \"X\"\n",
    "\n",
    "\n",
    "    def get_id(self, x, y, h):\n",
    "        return x + y * h\n",
    "\n",
    "    def get_legal_move(self, x, y, x_limit, y_limit):\n",
    "        ret = []\n",
    "        for item in self.select_move:\n",
    "            cur_x, cur_y = x - item[0], y - item[1]\n",
    "            if 0 <= cur_x < x_limit and 0 <= cur_y < y_limit:\n",
    "                ret.append((cur_x, cur_y))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # def dfs(matrix,r,c):\n",
    "        #     matrix[r][c] = 'X'\n",
    "        #     if r+1 < len(matrix) and matrix[r+1][c]=='O':\n",
    "        #         dfs(matrix,r+1,c)\n",
    "        #     if r-1 > 0 and matrix[r-1][c]=='O':\n",
    "        #         dfs(matrix,r-1,c)\n",
    "        #     if c+1 < len(matrix[0])and matrix[r][c+1]=='O':\n",
    "        #         dfs(matrix,r,c+1)\n",
    "        #     if c-1 > 0 and matrix[r][c-1]=='O':\n",
    "        #         dfs(matrix,r,c-1)\n",
    "        def bfs(matrix,r,c):\n",
    "            q = [[r,c]]\n",
    "            while q:\n",
    "                r,c = q.pop()\n",
    "                matrix[r][c] = 'X'\n",
    "                if r+1 < len(matrix) and matrix[r+1][c]=='O':\n",
    "                    q.append([r+1,c])\n",
    "                if r-1 > 0 and matrix[r-1][c]=='O':\n",
    "                    q.append([r-1,c])\n",
    "                if c+1 < len(matrix[0])and matrix[r][c+1]=='O':\n",
    "                    q.append([r,c+1])\n",
    "                if c-1 > 0 and matrix[r][c-1]=='O':\n",
    "                    q.append([r,c-1])\n",
    "\n",
    "\n",
    "        matrix = np.array(board)\n",
    "\n",
    "        for _ in range(4):\n",
    "            for i in range(len(matrix[0])):\n",
    "                if matrix[0][i] == 'O':\n",
    "                    bfs(matrix,0,i)\n",
    "            matrix = np.rot90(matrix)\n",
    "        \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 'O' and matrix[i][j] == 'O':\n",
    "                    board[i][j] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.select_move = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def solve(self, board: list[list[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 用字典保存每个顶点之间的边\n",
    "        edge = collections.defaultdict(list)\n",
    "        # 用唯一id映射矩阵中的每个顶点的，并标记是否被访问过，是否为x、o，如果为o是否临water\n",
    "        id_visited = {}\n",
    "        m, n = len(board), len(board[0])\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                cur_id = self.get_id(x, y, n)\n",
    "                id_visited[cur_id] = [board[y][x], x, y, \"white\", \"island\"]\n",
    "                cur_nbr_list = self.get_legal_move(x, y, n, m)\n",
    "                for nbr in cur_nbr_list:\n",
    "                    nbr_id = self.get_id(*nbr, n)\n",
    "                    edge[cur_id].append(nbr_id)\n",
    "                if len(cur_nbr_list) != 4:\n",
    "                    id_visited[cur_id][-1] = \"water\"\n",
    "        self.bfs(id_visited, board, edge)\n",
    "\n",
    "    def bfs(self, id_map: dict, board: list, edge: dict):\n",
    "        q = queue.Queue()\n",
    "        for k, v in id_map.items():\n",
    "            if v[0] == \"O\" and v[3] == \"white\":\n",
    "                cur_list = []\n",
    "                not_close_water = True\n",
    "                q.put(k)\n",
    "                while not q.empty():\n",
    "                    cur_id = q.get()\n",
    "                    id_map[cur_id][3] = \"black\"\n",
    "                    cur_list.append(cur_id)\n",
    "                    nbrs = edge.get(cur_id, [])\n",
    "                    if len(nbrs) != 4:\n",
    "                        not_close_water = False\n",
    "                    for nbr in nbrs:\n",
    "                        if id_map[nbr][0] == \"O\" and id_map[nbr][3] == \"white\":\n",
    "                            id_map[nbr][3] = \"gray\"\n",
    "                            cur_list.append(nbr)\n",
    "                            q.put(nbr)\n",
    "                if not_close_water:\n",
    "                    for bad in cur_list:\n",
    "                        bad_info = id_map[bad]\n",
    "                        board[bad_info[2]][bad_info[1]] = \"X\"\n",
    "\n",
    "    def get_id(self, x, y, h):\n",
    "        return x + y * h\n",
    "\n",
    "    def get_legal_move(self, x, y, x_limit, y_limit):\n",
    "        ret = []\n",
    "        for item in self.select_move:\n",
    "            cur_x, cur_y = x - item[0], y - item[1]\n",
    "            if 0 <= cur_x < x_limit and 0 <= cur_y < y_limit:\n",
    "                ret.append((cur_x, cur_y))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if not board or not board[0]:\n",
    "            return\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            board[i][j] = \"B\"\n",
    "            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                tmp_i = i + x\n",
    "                tmp_j = j + y\n",
    "                if 1 <= tmp_i < row and 1 <= tmp_j < col and board[tmp_i][tmp_j] == \"O\":\n",
    "                    dfs(tmp_i, tmp_j)\n",
    "\n",
    "        for j in range(col):\n",
    "            # 第一行\n",
    "            if board[0][j] == \"O\":\n",
    "                dfs(0, j)\n",
    "            # 最后一行\n",
    "            if board[row - 1][j] == \"O\":\n",
    "                dfs(row - 1, j)\n",
    "\n",
    "        for i in range(row):\n",
    "            # 第一列\n",
    "            if board[i][0] == \"O\":\n",
    "                dfs(i, 0)\n",
    "            # 最后一列\n",
    "            if board[i][col-1] == \"O\":\n",
    "                dfs(i, col - 1)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                # O 变成 X\n",
    "                if board[i][j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "                # B 变成 O\n",
    "                if board[i][j] == \"B\":\n",
    "                    board[i][j] = \"O\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    # self.is_bordr = \n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        n, m = len(board), len(board[0])\n",
    "        is_border = np.zeros((n, m))\n",
    "\n",
    "        for i in range(n):\n",
    "            self.dfs(i, 0, board, is_border)\n",
    "            self.dfs(i, m-1, board, is_border)\n",
    "        for j in range(m-1):\n",
    "            self.dfs(0, j, board, is_border)\n",
    "            self.dfs(n-1, j, board, is_border)\n",
    "\n",
    "        print(is_border)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                # if not is_border[i, j] and board[i][j] == 'O':\n",
    "                #     board[i][j] = 'X'\n",
    "                if board[i][j] == \"A\":\n",
    "                    board[i][j] = \"O\"\n",
    "                elif board[i][j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "\n",
    "    # 从边界蔓延\n",
    "    def dfs(self, i, j, board, is_border):\n",
    "        if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != 'O':\n",
    "            return\n",
    "        \n",
    "        board[i][j] = \"A\"\n",
    "\n",
    "        self.dfs(i+1, j, board, is_border)\n",
    "        self.dfs(i-1, j, board, is_border)\n",
    "        self.dfs(i, j+1, board, is_border)\n",
    "        self.dfs(i, j-1, board, is_border)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def join0(i, j, m, n):\n",
    "            for p, q in ([i-1, j], [i, j-1], [i+1, j], [i, j+1]):\n",
    "                if p >= 0 and p < m and q >= 0 and q < n and board[p][q] == \"O\" and unchange_map[p][q] == 0:\n",
    "                    unchange_map[p][q] = 1\n",
    "                    join0(p, q, m, n)\n",
    "\n",
    "        \n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return\n",
    "        import numpy as np\n",
    "        unchange_map = np.zeros([m, n])\n",
    "        for i in range(m):\n",
    "            if board[i][0] == \"O\" and unchange_map[i][0] == 0:\n",
    "                unchange_map[i][0] = 1\n",
    "                join0(i, 0, m, n)\n",
    "            if board[i][n-1] == \"O\" and unchange_map[i][n-1] == 0:\n",
    "                unchange_map[i][n-1] = 1\n",
    "                join0(i, n-1, m, n)\n",
    "        for j in range(1, n-1):\n",
    "            if board[0][j] == \"O\" and unchange_map[0][j] == 0:\n",
    "                unchange_map[0][j] = 1\n",
    "                join0(0, j, m, n)\n",
    "            if board[m-1][j] == \"O\" and unchange_map[m-1][j] == 0:\n",
    "                unchange_map[m-1][j] = 1\n",
    "                join0(m-1, j, m, n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "               if board[i][j] == \"O\" and unchange_map[i][j] == 0:\n",
    "                   board[i][j] = \"X\"\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "def dfs(B, i, j):\n",
    "    M, N = B.shape\n",
    "    if i >= M or i < 0 or j >= N or j < 0:\n",
    "        return None\n",
    "    if B[i, j] == \"O\":\n",
    "        B[i, j] = \"T\"\n",
    "        dfs(B, i-1, j)\n",
    "        dfs(B, i+1, j)\n",
    "        dfs(B, i, j-1)\n",
    "        dfs(B, i, j+1)\n",
    "    return None\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        B = np.array(board)\n",
    "        M, N = B.shape\n",
    "        for i in range(M):\n",
    "            dfs(B, i, j=0)\n",
    "            dfs(B, i, j=N-1)\n",
    "        for j in range(N):\n",
    "            dfs(B, i=0, j=j)\n",
    "            dfs(B, i=M-1, j=j)\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if B[i, j] == \"O\":\n",
    "                    board[i][j] = \"X\"\n",
    "                elif B[i, j] == \"T\":\n",
    "                    board[i][j] = \"O\"\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "        adj_list = collections.defaultdict(list)\n",
    "        pars = {}\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    pars[(i, j)] = -1\n",
    "                    if i + 1 < m and board[i+1][j] == 'O':\n",
    "                        edges.append(((i, j), (i+1, j)))\n",
    "                    if j + 1 < n and board[i][j+1] == 'O':\n",
    "                        edges.append(((i, j), (i, j+1)))\n",
    "\n",
    "        tree_size = {x: 1 for x in pars.keys()}\n",
    "        \n",
    "        def find_parents(node):\n",
    "            path = []\n",
    "            while pars[node] != -1:\n",
    "                node = pars[node]\n",
    "                path.append(node)\n",
    "            for n in path[:-1]:\n",
    "                pars[n] = node\n",
    "            \n",
    "            return node\n",
    "\n",
    "        def merge(node1, node2):\n",
    "            s1 = tree_size[node1]\n",
    "            s2 = tree_size[node2]\n",
    "            if s1 >= s2:\n",
    "                tree_size.pop(node2)\n",
    "                pars[node2] = node1\n",
    "                tree_size[node1] = s1 + s2\n",
    "            else:\n",
    "                tree_size.pop(node1)\n",
    "                pars[node1] = node2\n",
    "                tree_size[node2] = s1 + s2\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            p1 = find_parents(node1)\n",
    "            p2 = find_parents(node2)\n",
    "            if p1 != p2:\n",
    "                merge(p1, p2)\n",
    "            # print(node1, node2, pars, tree_size)\n",
    "\n",
    "        # print(pars)\n",
    "        # print(tree_size)\n",
    "\n",
    "        # Obtain each connected componet\n",
    "        compo = collections.defaultdict(list)\n",
    "        for node in pars.keys():\n",
    "            par = find_parents(node)\n",
    "            compo[par].append(node)\n",
    "        # print(compo)\n",
    "\n",
    "        for par, nodes in compo.items():\n",
    "            xs = [node[0] for node in nodes]\n",
    "            ys = [node[1] for node in nodes]\n",
    "            # print(xs, ys)\n",
    "            if min(xs) > 0 and max(xs) < m - 1 and min(ys) > 0 and max(ys) < n - 1:\n",
    "                for node in nodes:\n",
    "                    board[node[0]][node[1]] = 'X'\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        rows = len(board)\n",
    "        cols = len(board[0])\n",
    "        graph = [[[] for _ in range(cols)] for _ in range(rows)]\n",
    "        visited = [[0 for _ in range(cols)] for _ in range(rows)]\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                if board[row][col] == 'O':\n",
    "                    graph[row][col].append([row, col])\n",
    "                    if row > 0 and board[row-1][col] == 'O':\n",
    "                        graph[row][col].append([row-1, col])\n",
    "                    if row < rows-1 and board[row+1][col] == 'O':\n",
    "                        graph[row][col].append([row+1, col])\n",
    "                    if col > 0 and board[row][col-1] == 'O':\n",
    "                        graph[row][col].append([row, col-1])\n",
    "                    if col < cols-1 and board[row][col+1] == 'O':\n",
    "                        graph[row][col].append([row, col+1])\n",
    "\n",
    "        def traverse(row, col):\n",
    "            if visited[row][col]:\n",
    "                return\n",
    "            visited[row][col] = 1\n",
    "            for node in graph[row][col]:\n",
    "                if node == [row, col]:\n",
    "                    continue\n",
    "                else:\n",
    "                    traverse(node[0], node[1])\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if i == 0 or j == 0 or i == rows-1 or j == cols-1:\n",
    "                    if graph[i][j]:\n",
    "                        traverse(i, j)\n",
    "                    else:\n",
    "                        continue\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if visited[i][j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    board[i][j] = 'X'\n",
    "\n",
    "        return board\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        visited = np.zeros((m, n)).tolist()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O' and visited[i][j] == 0:\n",
    "                    self.bfs(board, i, j, m, n, visited)\n",
    "\n",
    "    def bfs(self, board, x, y, m, n, visited):\n",
    "        points = [(x, y)]\n",
    "        visited_points = [(x, y)]\n",
    "        direction = [-1, 0, 1, 0, -1]\n",
    "        visited[x][y] = 1\n",
    "        flag = False\n",
    "        while len(points) != 0:\n",
    "            point = points.pop(0)\n",
    "            for k in range(0, 4):\n",
    "                x_next = point[0] + direction[k]\n",
    "                y_next = point[1] + direction[k+1]\n",
    "                if x_next < 0 or y_next < 0 or x_next >= m or y_next >= n:\n",
    "                    flag = True\n",
    "                    continue\n",
    "                if board[x_next][y_next] == 'X':\n",
    "                    continue\n",
    "                if visited[x_next][y_next] == 0:\n",
    "                    visited[x_next][y_next] = 1\n",
    "                    points.append((x_next, y_next))\n",
    "                    visited_points.append((x_next, y_next))\n",
    "        \n",
    "        if not flag:\n",
    "            for point in visited_points:\n",
    "                board[point[0]][point[1]] = 'X'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, points, m, n):\n",
    "        self.points = {f\"{point[0]}_{point[1]}\":f\"{point[0]}_{point[1]}\"  for point in points}\n",
    "\n",
    "        # 记录当前集合是否靠近边界，默认为False\n",
    "        self.edge = {}\n",
    "        for point in points:\n",
    "            if point[0] == 0 or point[0] == m-1 or point[1] == 0 or point[1] == n-1:\n",
    "                self.edge[f\"{point[0]}_{point[1]}\"] = True\n",
    "            else:\n",
    "                self.edge[f\"{point[0]}_{point[1]}\"] = False\n",
    "\n",
    "    def queryEdge(self, x):\n",
    "        rx = self.find(x)\n",
    "        return self.edge[rx]\n",
    "\n",
    "    def find(self, x):\n",
    "        x = f\"{x[0]}_{x[1]}\"\n",
    "\n",
    "        # 排出异常x\n",
    "        while self.points[x] != x:\n",
    "            x = self.points[x]\n",
    "\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px = self.find(x)\n",
    "        py = self.find(y)\n",
    "\n",
    "        # 不需要合并\n",
    "        if px == py:\n",
    "            return\n",
    "\n",
    "        # 需要合并\n",
    "        self.points[py] = px\n",
    "        self.edge[px] = self.edge[px] or self.edge[py]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        # 查询所有的'O'，以及相邻关系\n",
    "        OPoints = []\n",
    "        edges = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    OPoints.append([i, j])\n",
    "\n",
    "                    # 上\n",
    "                    if i > 0 and board[i-1][j] == 'O':\n",
    "                        edges.add((i-1, j, i, j))\n",
    "                    # 下\n",
    "                    if i < m-1 and board[i+1][j] == 'O':\n",
    "                        edges.add((i, j, i+1, j))\n",
    "                    # 左\n",
    "                    if j > 0 and board[i][j-1] == 'O':\n",
    "                        edges.add((i, j-1, i, j))\n",
    "                    # 下\n",
    "                    if j < n-1 and board[i][j+1] == 'O':\n",
    "                        edges.add((i, j, i, j+1))\n",
    "\n",
    "        # 构建并查集\n",
    "        unionfind = UnionFindSet(OPoints, m, n)\n",
    "\n",
    "        # 合并相邻关系\n",
    "        for p1_x, p1_y, p2_x, p2_y  in edges:\n",
    "            unionfind.union((p1_x, p1_y), (p2_x, p2_y))\n",
    "\n",
    "        # 判断是否是边界\n",
    "        for point in OPoints:\n",
    "            if not unionfind.queryEdge(point):\n",
    "                board[point[0]][point[1]] = \"X\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conn(self, v, board):\n",
    "        i = v[0]\n",
    "        j = v[1]\n",
    "\n",
    "        if 0 < i < len(board) - 1 and 0 <j < len(board[0])-1:\n",
    "            return {(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)}\n",
    "\n",
    "        return {x for x in c if 0 <= x[0] <= len(board) - 1 and 0 <= x[1] <= len(board[0]) - 1}\n",
    "\n",
    "    def rtnUnvisitedConn(self, v, board, allZeros, visited):\n",
    "        return self.conn(v, board) & allZeros - visited\n",
    "\n",
    "    def capture(self, board, st):\n",
    "        for x in st:\n",
    "            board[x[0]][x[1]] = 'X'\n",
    "\n",
    "    def onBorder(self, v, board):\n",
    "        i = v[0]\n",
    "        j = v[1]\n",
    "        if i == 0 or i == len(board) - 1:\n",
    "            return True\n",
    "        if j == 0 or j == len(board[0]) - 1:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def allConnZeros(self, d, p):\n",
    "        s = set()\n",
    "        co = set(d[p])\n",
    "        x = co - s\n",
    "        s = s | co\n",
    "        while len(x):\n",
    "            co = set()\n",
    "            for i in x:\n",
    "                co = co | set(d[i])\n",
    "            x = co - s\n",
    "            s = s | co\n",
    "        return s\n",
    "\n",
    "\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        if board is None or len(board) == 0:\n",
    "            return\n",
    "        oX = set()\n",
    "        pendingZeros = set()\n",
    "        LEN1 = len(board)\n",
    "        LEN2 = len(board[0])\n",
    "        visited = set()\n",
    "        for i in range(LEN1):\n",
    "            for j in range(LEN2):\n",
    "                if board[i][j] == 'O':\n",
    "                    pendingZeros.add((i, j))\n",
    "        allZeros = pendingZeros\n",
    "        zeroCons = defaultdict(lambda: [])\n",
    "        for i, j in allZeros:\n",
    "            cons = {(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)} & allZeros\n",
    "            for x in cons:\n",
    "                zeroCons[(i,j)].append(x)\n",
    "\n",
    "        queue = deque([])\n",
    "        while len(pendingZeros) != 0:\n",
    "            p = pendingZeros.pop()\n",
    "            capture = True\n",
    "\n",
    "            s = self.allConnZeros(zeroCons, p)\n",
    "            s.add(p)\n",
    "            #print(p)\n",
    "            x = set([x for x, y in s])\n",
    "            if 0 in x or LEN1-1 in x:\n",
    "                capture = False\n",
    "            else:\n",
    "                y = set([y for x, y in s])\n",
    "                if 0 in y or LEN2-1 in y:\n",
    "                    capture = False\n",
    "\n",
    "            if capture:\n",
    "                oX = oX | s\n",
    "\n",
    "            pendingZeros = pendingZeros - s\n",
    "        for x in oX:\n",
    "            board[x[0]][x[1]] = 'X'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import numpy as np\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "        \n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index_i = i * n + j\n",
    "                if j < n - 1 and board[i][j] == 'O' and board[i][j + 1] == 'O':\n",
    "                    uf.union(index_i, index_i + 1)\n",
    "                if i < m - 1 and board[i][j] == 'O' and board[i + 1][j] == 'O':\n",
    "                    index_j = (i + 1) * n + j\n",
    "                    uf.union(index_i, index_j)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    index = i * n + j\n",
    "                    graph[uf.find(index)].append([i, j])\n",
    "\n",
    "        for k, v in graph.items():\n",
    "            np_v = np.array(v)\n",
    "            v_i = np_v[:,0]\n",
    "            v_j = np_v[:,1]\n",
    "            if 0 in v_i or m-1 in v_i:\n",
    "                continue\n",
    "            if 0 in v_j or n-1 in v_j:\n",
    "                continue\n",
    "            for i, j in v:\n",
    "                board[i][j] = 'X'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import numpy as np\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and board[i][j] == 'O' and board[i][j + 1] == 'O':\n",
    "                    uf.union(index, index + 1)\n",
    "                if i < m - 1 and board[i][j] == 'O' and board[i + 1][j] == 'O':\n",
    "                    index_j = (i + 1) * n + j\n",
    "                    uf.union(index, index_j)\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    graph[uf.find(i * n + j)].append([i, j])\n",
    "\n",
    "        for k, v in graph.items():\n",
    "            np_o = np.array(v)\n",
    "            np_x = np_o[:, 0]\n",
    "            np_y = np_o[:, 1]\n",
    "            if 0 in np_x or m - 1 in np_x:\n",
    "                continue\n",
    "            if 0 in np_y or n - 1 in np_y:\n",
    "                continue\n",
    "            for i, j in v:\n",
    "                board[i][j] = 'X'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        nb={}\n",
    "        self.flag=True\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                # if board[i][j]=='X':\n",
    "                #     flag=False\n",
    "                nb[(i,j)]=set()\n",
    "                if i>=0 and j-1>=0:\n",
    "                    nb[(i,j)].add((i,j-1))\n",
    "                if i>=0 and j+1<len(board[0]):\n",
    "                    nb[(i,j)].add((i,j+1))\n",
    "                if j+1<len(board[0]) and i<len(board):\n",
    "                    nb[(i,j)].add((i,j+1))\n",
    "                if j<len(board[0]) and i-1>=0:\n",
    "                    nb[(i,j)].add((i-1,j))\n",
    "                if j<len(board[0]) and i+1<len(board):\n",
    "                    nb[(i,j)].add((i+1,j))\n",
    "        \n",
    "\n",
    "        self.b=False\n",
    "        def dfs(point):\n",
    "            visited=set()\n",
    "            stack=[point]\n",
    "            while len(stack):\n",
    "                p=stack.pop()\n",
    "                c=0\n",
    "\n",
    "                for neighbor in nb[p]:\n",
    "\n",
    "                    if p==point and board[neighbor[0]][neighbor[1]] == \"X\":\n",
    "                        c+=1\n",
    "                    if board[neighbor[0]][neighbor[1]] == \"O\" and (neighbor[0]==0 or neighbor[0]==len(board)-1 or neighbor[1]==0 or neighbor[1]==len(board[0])-1):\n",
    "                        self.b=True\n",
    "                        #visited=set()\n",
    "                        return visited\n",
    "                    if board[neighbor[0]][neighbor[1]] == \"O\" and neighbor[0]!=0 and neighbor[0]!=len(board)-1 and neighbor[1]!=0 and neighbor[1]!=len(board[0])-1 and (neighbor not in visited):\n",
    "                        stack.append(neighbor)\n",
    "                        visited.add(neighbor)\n",
    "                if c==4 and len(visited)==0:\n",
    "                    #print(\"j\")\n",
    "                    self.flag=False\n",
    "            return visited\n",
    "        v=[]\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j]=='O' and i!=0 and i!=len(board)-1 and j!=0 and j!=len(board[0])-1 and board[i][j] not in v:\n",
    "                    #print((i,j))\n",
    "                    # board[i][j]=\"X\"\n",
    "                    area=dfs((i,j))\n",
    "                    if self.b:\n",
    "                        v.extend(list(area))\n",
    "                        self.b=False\n",
    "                    else:\n",
    "                        print(area)\n",
    "                        for p in area:\n",
    "                            board[p[0]][p[1]]=\"X\" \n",
    "                        if len(area) or not self.flag:\n",
    "                            #print(\"!\")\n",
    "                            board[i][j]=\"X\"  \n",
    "                            self.flag=True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if len(board) <= 2 or len(board[0]) <= 2:\n",
    "            return board\n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if i == 0 or j ==0 or i == len(board) - 1 or j == len(board[0]) - 1:\n",
    "                    if board[i][j] == 'O':\n",
    "                        self.dfs(i, j, board, 'Y')\n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if board[i][j] == 'O':\n",
    "                    self.dfs(i, j, board, 'X') \n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if board[i][j] == 'Y':\n",
    "                    board[i][j] = 'O'\n",
    "        return board\n",
    "    def dfs(self, i, j, board, char):\n",
    "        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] != 'O':\n",
    "            return \n",
    "        board[i][j] = char\n",
    "        self.dfs(i - 1, j, board, char)\n",
    "        self.dfs(i + 1, j, board, char)\n",
    "        self.dfs(i, j - 1, board, char)\n",
    "        self.dfs(i, j + 1, board, char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if len(board) <= 2 or len(board[0]) <= 2:\n",
    "            return board\n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if board[i][j] == 'O' and (i == 0 or j ==0 or i == len(board) - 1 or j == len(board[0]) - 1):\n",
    "                    self.dfs(i, j, board, 'Y')\n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if board[i][j] == 'O':\n",
    "                    self.dfs(i, j, board, 'X') \n",
    "        for i in range(0, len(board)):\n",
    "            for j in range(0, len(board[0])):\n",
    "                if board[i][j] == 'Y':\n",
    "                    board[i][j] = 'O'\n",
    "        return board\n",
    "    def dfs(self, i, j, board, char):\n",
    "        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] != 'O':\n",
    "            return \n",
    "        board[i][j] = char\n",
    "        self.dfs(i - 1, j, board, char)\n",
    "        self.dfs(i + 1, j, board, char)\n",
    "        self.dfs(i, j - 1, board, char)\n",
    "        self.dfs(i, j + 1, board, char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        status = [[0] * len(t) for t in board]\n",
    "\n",
    "        def dp(x, y, is_success, s):\n",
    "            new_direction = []\n",
    "            direction = ((1, 0), (-1, 0), (0, -1), (0, 1))\n",
    "            for x_i, y_i in direction:\n",
    "                n_x, n_y = x + x_i, y + y_i\n",
    "                if n_x < 0 or n_x >= len(board):\n",
    "                    is_success &= False\n",
    "                    continue\n",
    "                if n_y < 0 or n_y >= len(board[0]):\n",
    "                    is_success &= False\n",
    "                    continue\n",
    "                if board[n_x][n_y] == \"X\":\n",
    "                    continue\n",
    "                if status[n_x][n_y] == 2:\n",
    "                    continue\n",
    "                status[n_x][n_y] = 2\n",
    "                new_direction.append((n_x, n_y))\n",
    "\n",
    "            s.update(new_direction)\n",
    "            for n_x, n_y in new_direction:\n",
    "                is_success &= dp(n_x, n_y, is_success, s)\n",
    "            return is_success\n",
    "\n",
    "        for i in range(1, len(board)):\n",
    "            for j in range(1, len(board[0])):\n",
    "                if status[i][j] == \"-1\":\n",
    "                    continue\n",
    "                if board[i][j] == \"O\":\n",
    "                    t = set()\n",
    "                    t.add((i, j))\n",
    "                    ret = dp(i, j, True, t)\n",
    "                    for x_i, y_i in t:\n",
    "                        status[x_i][y_i] = -1\n",
    "                        if ret:\n",
    "                            board[x_i][y_i] = \"X\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, x, y):\n",
    "        if x < 0 or y < 0 or x >= len(self.flag) or y >= len(self.flag[0]):\n",
    "            self.f = 1\n",
    "            return\n",
    "        if  self.b[x][y] == 'X' or self.flag[x][y] == 1:return\n",
    "        self.flag[x][y] = 1\n",
    "        self.path.append((x,y))\n",
    "        self.dfs(x+1,y)\n",
    "        self.dfs(x-1,y)\n",
    "        self.dfs(x,y+1)\n",
    "        self.dfs(x,y-1)\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.flag = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]\n",
    "        self.b = board\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if self.flag[i][j] == 1 or board[i][j] == 'X':continue\n",
    "                self.path = []\n",
    "                self.f = 0\n",
    "                self.dfs(i,j)\n",
    "                if len(self.path)!=0 and self.f == 0:\n",
    "                    for z in range(len(self.path)):\n",
    "                        board[self.path[z][0]][self.path[z][1]] = 'X'\n",
    "        return board\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.a = []\n",
    "        self.book = []\n",
    "        self.next = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "        self.m = 0\n",
    "        self.n = 0\n",
    "\n",
    "    def solve(self, board) -> None:\n",
    "        if not board:\n",
    "            return []\n",
    "        self.a = board\n",
    "        self.m, self.n = len(board), len(board[0])\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if self.a[i][j] == 'O' and (j==0 or j==self.n-1 or i==0 or i==self.m-1):\n",
    "                    self.a[i][j] = '.'\n",
    "                    self.dfs(i, j, '.')\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if self.a[i][j] == 'O':\n",
    "                    self.a[i][j] = 'X'\n",
    "                    self.dfs(i, j, 'X')\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if self.a[i][j] == '.':\n",
    "                    self.a[i][j] = 'O'\n",
    "\n",
    "    def dfs(self, x, y, spe):\n",
    "        for i in range(4):\n",
    "            tx = x + self.next[i][0]\n",
    "            ty = y + self.next[i][1]\n",
    "            if tx >= 0 and ty >= 0 and tx < self.m and ty < self.n and self.a[tx][ty] == 'O':\n",
    "                self.a[tx][ty] = spe\n",
    "                self.dfs(tx, ty, spe)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.rows = None\n",
    "        self.columns = None\n",
    "        self.visited = None\n",
    "        self.direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "    def solve(self, board) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.rows = len(board)\n",
    "        if not self.rows:\n",
    "            return board\n",
    "\n",
    "        self.columns = len(board[0])\n",
    "\n",
    "        if self.rows <= 2 or self.columns <= 2:\n",
    "            return board\n",
    "\n",
    "        self.visited = [[False for _ in range(self.columns)] for _ in range(self.rows)]\n",
    "\n",
    "        # i，j肯定在区域内，且不是边缘数据，\n",
    "        for i in range(1, self.rows - 1):\n",
    "            for j in range(1, self.columns - 1):\n",
    "                if board[i][j] == \"O\" and not self.visited[i][j]:\n",
    "                    self.dfs(board, i, j)\n",
    "\n",
    "    def dfs(self, board, startx, starty):\n",
    "\n",
    "        self.visited[startx][starty] = True\n",
    "        board[startx][starty] = 'X'\n",
    "\n",
    "        for i in range(4):\n",
    "            new_startx = startx + self.direction[i][0]\n",
    "            new_starty = starty + self.direction[i][1]\n",
    "\n",
    "            # 判断new_startx, new_starty是否是有效的 在区域内，且不是边缘数据\n",
    "            if self.is_area(new_startx, new_starty)\\\n",
    "                and board[new_startx][new_starty] == 'O':\n",
    "\n",
    "                if not self.visited[new_startx][new_starty]:\n",
    "                    if self.is_not_edge(new_startx, new_starty):\n",
    "\n",
    "                        self.dfs(board, new_startx, new_starty)\n",
    "                    else:\n",
    "                        self.re_dfs(board, startx, starty)\n",
    "                        return\n",
    "                else:\n",
    "                    self.re_dfs(board, startx, starty)\n",
    "                    return\n",
    "        return\n",
    "\n",
    "    def re_dfs(self, board, startx, starty):\n",
    "\n",
    "        board[startx][starty] = 'O'\n",
    "\n",
    "        for i in range(4):\n",
    "            new_startx = startx + self.direction[i][0]\n",
    "            new_starty = starty + self.direction[i][1]\n",
    "\n",
    "            # 注：self.visited[new_startx][new_starty] == True\n",
    "            # new_startx, new_starty 就不会是边缘数据\n",
    "            if self.is_area(new_startx, new_starty)\\\n",
    "                and self.visited[new_startx][new_starty]\\\n",
    "                and board[new_startx][new_starty] == 'X':\n",
    "\n",
    "                self.re_dfs(board, new_startx, new_starty)\n",
    "        return\n",
    "\n",
    "\n",
    "    def is_not_edge(self, startx, starty):\n",
    "        return startx > 0 and startx < self.rows - 1 \\\n",
    "               and starty > 0 and starty < self.columns - 1\n",
    "\n",
    "    def is_area(self, startx, starty):\n",
    "        return startx >= 0 and startx < self.rows\\\n",
    "               and starty >= 0 and starty < self.columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def border_check(grid: tuple, size: int):\n",
    "    if grid[0] < 1 or grid[1] < 1:\n",
    "        return False\n",
    "    elif grid[0] + 2 > size[0] or grid[1] + 2 > size[1]:\n",
    "        return False\n",
    "    else:\n",
    "        return True\n",
    "\n",
    "\n",
    "def dfs_search(res_list: list, mask_matrix: list, grid: tuple, error_list: list):\n",
    "    if mask_matrix[grid[0]][grid[1]] == 'O':\n",
    "        if border_check(grid, (len(mask_matrix), len(mask_matrix[0]))):\n",
    "            res_list.append(grid)\n",
    "            mask_matrix[grid[0]][grid[1]] = 'X'\n",
    "            dfs_search(res_list, mask_matrix, (grid[0] + 1, grid[1]), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0], grid[1] + 1), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0] - 1, grid[1]), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0], grid[1] - 1), error_list)\n",
    "        else:\n",
    "            error_list.append(grid)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if len(board) > 2:\n",
    "            mask = list()\n",
    "            for line in board:\n",
    "                mask.append(list(line))\n",
    "            for i in range(1, len(board) - 1):\n",
    "                for j in range(1, len(board[0]) - 1):\n",
    "                    search_res = list()\n",
    "                    errors = list()\n",
    "                    dfs_search(search_res, mask, (i, j), errors)\n",
    "                    if len(search_res) > 0 and len(errors) == 0:  # 找到一个包围图形\n",
    "                        for grid in search_res:\n",
    "                            board[grid[0]][grid[1]] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def border_check(grid: tuple, size: int):\n",
    "    if grid[0] < 1 or grid[1] < 1:\n",
    "        return False\n",
    "    elif grid[0] + 2 > size[0] or grid[1] + 2 > size[1]:\n",
    "        return False\n",
    "    else:\n",
    "        return True\n",
    "\n",
    "\n",
    "def dfs_search(res_list: list, mask_matrix: list, grid: tuple, error_list: list):\n",
    "    if mask_matrix[grid[0]][grid[1]] == 'O':\n",
    "        if border_check(grid, (len(mask_matrix), len(mask_matrix[0]))):\n",
    "            res_list.append(grid)\n",
    "            mask_matrix[grid[0]][grid[1]] = 'X'\n",
    "            dfs_search(res_list, mask_matrix, (grid[0] + 1, grid[1]), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0], grid[1] + 1), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0] - 1, grid[1]), error_list)\n",
    "            dfs_search(res_list, mask_matrix, (grid[0], grid[1] - 1), error_list)\n",
    "        else:\n",
    "            error_list.append(grid)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if len(board) > 2:\n",
    "            mask = list()\n",
    "            for line in board:\n",
    "                mask.append(list(line))\n",
    "            for i in range(1, len(board) - 1):\n",
    "                for j in range(1, len(board[0]) - 1):\n",
    "                    search_res = list()\n",
    "                    errors = list()\n",
    "                    dfs_search(search_res, mask, (i, j), errors)\n",
    "                    if len(search_res) > 0 and len(errors) == 0:  # 找到一个包围图形\n",
    "                        for grid in search_res:\n",
    "                            board[grid[0]][grid[1]] = 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board, x, y, row, col, path):\n",
    "        if x < 0 or x >= row or y < 0 or y >= col:\n",
    "            return False\n",
    "        if board[x][y] != 'O':\n",
    "            return True\n",
    "        board[x][y] = 'P'\n",
    "\n",
    "        path.append((x, y))\n",
    "\n",
    "        up = self.dfs(board, x - 1, y, row, col, path)\n",
    "        right = self.dfs(board, x, y + 1, row, col, path)\n",
    "        down = self.dfs(board, x + 1, y, row, col, path)\n",
    "        left = self.dfs(board, x, y - 1, row, col, path)\n",
    "\n",
    "        return up and right and down and left\n",
    "\n",
    "\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        row = len(board)\n",
    "        if row == 0:\n",
    "            return\n",
    "        col = len(board[0])\n",
    "        if col == 0:\n",
    "            return\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == 'O':\n",
    "                    path = []\n",
    "                    if self.dfs(board, i, j, row, col, path) is True:\n",
    "                        for coord in path:\n",
    "                            board[coord[0]][coord[1]] = 'X'\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                board[i][j] = 'O' if board[i][j] == 'P' else 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if not board:\n",
    "            return\n",
    "\n",
    "        row_num, col_num = len(board), len(board[0])\n",
    "\n",
    "        island_idx = 0\n",
    "        for y_idx in range(row_num):\n",
    "            for x_idx in range(col_num):\n",
    "                self._infect(board, y_idx, x_idx, island_idx)\n",
    "                island_idx += 1\n",
    "\n",
    "        border_island_idxs = {...}\n",
    "        for y_idx in range(row_num):\n",
    "            if board[y_idx][0] != 'X':\n",
    "                border_island_idxs.add(board[y_idx][0])\n",
    "            if board[y_idx][col_num - 1] != 'X':\n",
    "                border_island_idxs.add(board[y_idx][col_num - 1])\n",
    "        for x_idx in range(col_num):\n",
    "            if board[0][x_idx] != 'X':\n",
    "                border_island_idxs.add(board[0][x_idx])\n",
    "            if board[row_num - 1][x_idx] != 'X':\n",
    "                border_island_idxs.add(board[row_num - 1][x_idx])\n",
    "\n",
    "        for y_idx in range(row_num):\n",
    "            for x_idx in range(col_num):\n",
    "                if board[y_idx][x_idx] != 'X':\n",
    "                    if board[y_idx][x_idx] not in border_island_idxs:\n",
    "                        board[y_idx][x_idx] = 'X'\n",
    "                    else:\n",
    "                        board[y_idx][x_idx] = 'O'\n",
    "\n",
    "        return\n",
    "\n",
    "    def _infect(self, board: List[List[str]], y_idx: int, x_idx: int, island_idx: int) -> None:\n",
    "        if y_idx < 0 or y_idx >= len(board) or x_idx < 0 or x_idx >= len(board[0]):\n",
    "            return\n",
    "        if board[y_idx][x_idx] == 'O':\n",
    "            board[y_idx][x_idx] = island_idx\n",
    "            self._infect(board, y_idx + 1, x_idx, island_idx)\n",
    "            self._infect(board, y_idx - 1, x_idx, island_idx)\n",
    "            self._infect(board, y_idx, x_idx + 1, island_idx)\n",
    "            self._infect(board, y_idx, x_idx - 1, island_idx)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def infect(self, i, j, chara, board):\n",
    "        if board[i][j] == 'O':\n",
    "            board[i][j] = chara\n",
    "            if i - 1 >= 0:\n",
    "                self.infect(i - 1, j, chara, board)\n",
    "            if i + 1 < len(board):\n",
    "                self.infect(i + 1, j, chara, board)\n",
    "            if j - 1 >= 0:\n",
    "                self.infect(i, j - 1, chara, board)\n",
    "            if j + 1 < len(board[0]):\n",
    "                self.infect(i, j + 1, chara, board)\n",
    "\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 先从最外面一圈开始感染，感染过的地方先填充#，最后变回O\n",
    "        # 然后去掉最外面一圈，正常感染\n",
    "        n, m = len(board), len(board[0])\n",
    "        for i in range(n):\n",
    "            self.infect(i, 0, '#', board)\n",
    "            self.infect(i, m - 1, '#', board)\n",
    "        for j in range(m):\n",
    "            self.infect(0, j, '#', board)\n",
    "            self.infect(n - 1, j, '#', board)\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(1, m - 1):\n",
    "                self.infect(i, j, 'X', board)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if board[i][j] == '#':\n",
    "                    board[i][j] = 'O'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Tuple\n",
    "\n",
    "directions = [\n",
    "    [0, 1],\n",
    "    [0, -1],\n",
    "    [1, 0],\n",
    "    [-1, 0],\n",
    "]\n",
    "\n",
    "def _is_boundary(x: int, y: int, len_x: int, len_y: int) -> bool:\n",
    "    return (x == 0) or (x == len_x - 1) or (y == 0) or (y == len_y - 1)\n",
    "\n",
    "def _replace_boundary(board: List[List[str]],\n",
    "                      source: str, dest: str) -> None:\n",
    "    for x in range(len(board)):\n",
    "        if x == 0 or x == len(board)-1:\n",
    "            for y in range(len(board[0])):\n",
    "                if board[x][y] == source:\n",
    "                    board[x][y] = dest\n",
    "        else:\n",
    "            if board[x][0] == source:\n",
    "                board[x][0] = dest\n",
    "            if board[x][-1] == source:\n",
    "                board[x][-1] = dest\n",
    "\n",
    "def dfs(board: List[List[str]],\n",
    "        x: int, y: int,\n",
    "        vis: List[List[bool]],\n",
    "        path: List[Tuple[int, int]]) -> List[Tuple[int, int]]:\n",
    "    if board[x][y] == 'B':\n",
    "        return []\n",
    "\n",
    "    vis[x][y] = True\n",
    "    path.append((x, y))\n",
    "    reach_boundary = False\n",
    "    for dx, dy in directions:\n",
    "        new_x = x + dx\n",
    "        new_y = y + dy\n",
    "        if board[new_x][new_y] in 'BO' and not vis[new_x][new_y]:\n",
    "            path = dfs(board, new_x, new_y, vis, path)\n",
    "        if not path:\n",
    "            reach_boundary = True\n",
    "    \n",
    "    return [] if reach_boundary else path\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        vis = [[False for _ in row] for row in board]\n",
    "\n",
    "        _replace_boundary(board, 'O', 'B')\n",
    "        \n",
    "        for x, row in enumerate(board):\n",
    "            for y, elem in enumerate(row):\n",
    "                if elem == 'O' and not vis[x][y]:\n",
    "                    path = dfs(board, x, y, vis, [])\n",
    "                    for px, py in path:\n",
    "                        board[px][py] = 'X'\n",
    "        \n",
    "        _replace_boundary(board, 'B', 'O')\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        visited = [[False for i in range(len(board[0]))] for j in range(len(board))]\n",
    "        for sx in range(len(board)):\n",
    "            for sy in range(len(board[0])):\n",
    "                path = []\n",
    "                if not visited[sx][sy] and board[sx][sy] == 'O' and self.flooding(board, path, sx, sy, visited):\n",
    "                    for x, y in path:\n",
    "                        board[x][y] = 'X'\n",
    "    \n",
    "\n",
    "    def flooding(self, board, path, x, y, visited):\n",
    "        path.append((x, y))\n",
    "        visited[x][y] = True\n",
    "        surrounded = (x != 0 and x != len(board)-1 and y != 0 and y != len(board[0])-1)\n",
    "        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "            tx, ty = x+dx, y+dy \n",
    "            if tx < 0 or tx >= len(board) or ty < 0 or ty >= len(board[0]): \n",
    "                continue \n",
    "            if visited[tx][ty] or board[tx][ty] == 'X':\n",
    "                continue\n",
    "            surrounded = self.flooding(board, path, tx, ty, visited) and surrounded\n",
    "        return surrounded\n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        self.N=len(board)\n",
    "        self.M=len(board[0])\n",
    "        for i in range(1,self.N-1):\n",
    "            for j in range(1,self.M-1):\n",
    "                if board[i][j]=='O':\n",
    "                    self.Have = [[True] * self.M for _ in range(self.N)]\n",
    "                    if self.OK(board,i,j):\n",
    "                        self.chage(board,i,j)\n",
    "        #print(board)\n",
    "    def OK(self,A,i,j):\n",
    "        if i==0 or i==self.N-1 or j==0 or j==self.M-1:\n",
    "            if A[i][j]=='O':\n",
    "                return False\n",
    "            else:\n",
    "                return  True\n",
    "        else :\n",
    "            if A[i][j]=='X':\n",
    "                return True\n",
    "            else:\n",
    "                if self.Have[i][j]:\n",
    "                    self.Have[i][j]=False\n",
    "                    return self.OK(A,i-1,j) and self.OK(A,i+1,j) and self.OK(A,i,j-1) and self.OK(A,i,j+1)\n",
    "                else:\n",
    "                    return True\n",
    "    def chage(self,A,i,j):\n",
    "        if A[i][j]=='O':\n",
    "            A[i][j]='X'\n",
    "            self.chage(A,i-1,j)\n",
    "            self.chage(A, i + 1, j)\n",
    "            self.chage(A, i, j-1)\n",
    "            self.chage(A, i, j+1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    Direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def solve(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not board and not board[0]:\n",
    "            return 0\n",
    "        self._grid = board\n",
    "        self._R, self._C = len(board), len(board[0])\n",
    "        self._visited = [[False] * self._C for _ in range(self._R)]\n",
    "        for i in range(self._R):\n",
    "            if board[i][0] == \"O\":\n",
    "                self.dfs_initial_boundary(i, 0)\n",
    "                # self.bfs_initial_boundary(i, 0)\n",
    "            if board[i][self._C - 1] == \"O\":\n",
    "                self.dfs_initial_boundary(i, self._C - 1)\n",
    "                # self.bfs_initial_boundary(i, self._C - 1)\n",
    "        for j in range(self._C):\n",
    "            if board[0][j] == \"O\":\n",
    "                self.dfs_initial_boundary(0, j)\n",
    "                # self.bfs_initial_boundary(0, j)\n",
    "            if board[self._R - 1][j] == \"O\":\n",
    "                self.dfs_initial_boundary(self._R - 1, j)\n",
    "                # self.bfs_initial_boundary(self._R - 1, j)\n",
    "        for x in range(self._R):\n",
    "            for y in range(self._C):\n",
    "                if not self._visited[x][y] and self._grid[x][y] == \"O\":\n",
    "                    self.dfs(x, y)\n",
    "\n",
    "        for x in range(self._R):\n",
    "            for y in range(self._C):\n",
    "                if self._grid[x][y] == 2:\n",
    "                    self._grid[x][y] = \"O\"\n",
    "        return self._grid\n",
    "\n",
    "    def inArea(self, x, y):\n",
    "        return 0 <= x < self._R and 0 <= y < self._C\n",
    "\n",
    "    def dfs_initial_boundary(self, x, y):\n",
    "        self._visited[x][y] = True\n",
    "        self._grid[x][y] = 2\n",
    "        for dx, dy in self.Direction:\n",
    "            nextx = x + dx\n",
    "            nexty = y + dy\n",
    "            if self.inArea(nextx, nexty) and not self._visited[nextx][nexty] \\\n",
    "                    and self._grid[nextx][nexty] == \"O\":\n",
    "                self.dfs_initial_boundary(nextx, nexty)\n",
    "\n",
    "    # def dfs_return_boundary(self, x, y):\n",
    "    #     self._visited[x][y] = True\n",
    "    #     self._grid[x][y] = \"O\"\n",
    "    #     for dx, dy in self.Direction:\n",
    "    #         nextx = x + dx\n",
    "    #         nexty = y + dy\n",
    "    #         if self.inArea(nextx, nexty) and not self._visited[nextx][nexty] \\\n",
    "    #                 and self._grid[nextx][nexty] == 2:\n",
    "    #             self.dfs_return_boundary(nextx, nexty)\n",
    "\n",
    "    def dfs(self, x, y):\n",
    "        self._visited[x][y] = True\n",
    "        self._grid[x][y] = \"X\"\n",
    "        for dx, dy in self.Direction:\n",
    "            nextx = x + dx\n",
    "            nexty = y + dy\n",
    "            if self.inArea(nextx, nexty) and not self._visited[nextx][nexty] \\\n",
    "                    and self._grid[nextx][nexty] == \"O\":\n",
    "                self.dfs(nextx, nexty)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        self.directX, self.directY = [0,0,1,-1], [1,-1,0,0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0 or i == m-1 or j == n-1:\n",
    "                    if board[i][j] == \"O\":\n",
    "                        self.visited = set()\n",
    "                        self.visited.add((i, j))\n",
    "                        self.dfs(board, i, j, \"O\", \"#\")\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\":\n",
    "                    self.visited = set()\n",
    "                    self.visited.add((i, j))\n",
    "                    self.dfs(board, i, j, \"O\", \"X\")\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"#\":\n",
    "                    self.visited = set()\n",
    "                    self.visited.add((i, j))\n",
    "                    self.dfs(board, i, j, \"#\", \"O\")\n",
    "\n",
    "    \n",
    "    def dfs(self, board, x, y, old_stone, new_stone):\n",
    "\n",
    "        board[x][y] = new_stone\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        for k in range(4):\n",
    "            new_x, new_y = x + self.directX[k], y + self.directY[k]\n",
    "            if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:\n",
    "                continue\n",
    "            if board[new_x][new_y] == old_stone:\n",
    "                self.dfs(board, new_x, new_y, old_stone, new_stone)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        self.directX, self.directY = [0,0,1,-1], [1,-1,0,0]\n",
    "        for j in range(n):\n",
    "            if board[0][j] == 'O':\n",
    "                self.dfs(board, 0, j, 'O', 'Y')\n",
    "            if board[m-1][j] == 'O':\n",
    "                self.dfs(board, m-1, j, 'O', 'Y')\n",
    "        \n",
    "        for i in range(1, m-1):\n",
    "            if board[i][0] == 'O':\n",
    "                self.dfs(board, i, 0, 'O', 'Y')\n",
    "            if board[i][n-1] == 'O':\n",
    "                self.dfs(board, i, n-1, 'O', 'Y')\n",
    "        \n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                if board[i][j] == 'O':\n",
    "                    self.dfs(board, i, j, 'O', 'X')\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'Y':\n",
    "                    board[i][j] = 'O'\n",
    "    \n",
    "    def dfs(self, board, x, y, from_stone, to_stone):\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        \n",
    "        board[x][y] = to_stone\n",
    "        for k in range(4):\n",
    "            new_x, new_y = x + self.directX[k], y + self.directY[k]\n",
    "            if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:\n",
    "                continue\n",
    "            if board[new_x][new_y] == from_stone:\n",
    "                self.dfs(board, new_x, new_y, from_stone, to_stone)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        row, cols = len(board), len(board[0])\n",
    "        used = [[False for _ in range(cols)] for _ in range(row)]\n",
    "        directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}\n",
    "        for i in range(row):\n",
    "            for j in range(cols):\n",
    "                if i == 0 or i == row-1 or j == 0 or j == cols-1:\n",
    "                    if board[i][j] == 'O' and used[i][j] == False:\n",
    "                        #先对比board数组，将与边界有关的字母O对应的used数组将其变为True\n",
    "                        self.dfs_1(board, i, j, row, cols, used, directions)\n",
    "        for i in range(1, row-1):\n",
    "            for j in range(1, cols-1):\n",
    "                if board[i][j] == 'O' and used[i][j] == False:\n",
    "                    #对比used数组，再将board数组进行改变\n",
    "                    self.dfs_2(board, i, j, row, cols, used, directions)\n",
    "        return board\n",
    "    \n",
    "    def dfs_1(self, board, i, j, row, cols, used, directions):\n",
    "        used[i][j] = True\n",
    "        for direction in directions:\n",
    "            new_i = i + direction[0]\n",
    "            new_j = j + direction[1]\n",
    "            if 0<=new_i<row and 0<=new_j<cols and board[new_i][new_j] == 'O' and used[new_i][new_j] == False:\n",
    "                used[new_i][new_j] = True\n",
    "                self.dfs_1(board, new_i, new_j, row, cols, used, directions)\n",
    "\n",
    "    def dfs_2(self, board, i, j, row, cols, used, directions):\n",
    "        board[i][j] = 'X'\n",
    "        for direction in directions:\n",
    "            new_i = i + direction[0]\n",
    "            new_j = j + direction[1]\n",
    "            if 1<=new_i<row-1 and 1<=new_j<cols-1 and board[new_i][new_j] == 'O' and used[new_i][new_j] == False:\n",
    "                board[new_i][new_j] = 'X'\n",
    "                self.dfs_2(board, new_i, new_j, row, cols, used, directions)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if (i==0 or i==len(board)-1 or j==0 or j==len(board[0])-1) and board[i][j]=='O':\n",
    "                    self.find(board,i,j,'O','*')\n",
    "        for i in range(1,len(board)-1):\n",
    "            for j in range(1,len(board[0])-1):\n",
    "                if board[i][j]=='O':\n",
    "                    self.find(board,i,j,'O','X')\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if (i==0 or i==len(board)-1 or j==0 or j==len(board[0])-1) and board[i][j]=='*':\n",
    "                    self.find(board,i,j,'*','O')\n",
    "    \n",
    "    def find(self,strs,x,y,str1,str2):\n",
    "        strs[x][y]=str2\n",
    "        for dx,dy in [(1,0),(0,-1),(-1,0),(0,1)]:\n",
    "            if 0<=x+dx<len(strs) and 0<=y+dy<len(strs[0]) and strs[x+dx][y+dy]==str1:\n",
    "                self.find(strs,x+dx,y+dy,str1,str2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "m, n = 0, 0\n",
    "\n",
    "\n",
    "def dfs(x, y, board, visited, flag):\n",
    "    if visited[x][y]:\n",
    "        return\n",
    "    visited[x][y] = 1\n",
    "    if flag:\n",
    "        board[x][y] = 'X'\n",
    "    for i in range(4):\n",
    "        nx = x + dirs[i][0]\n",
    "        ny = y + dirs[i][1]\n",
    "        if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == 0 and board[nx][ny] == 'O':\n",
    "            dfs(nx, ny, board, visited, flag)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def solve(board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        global m, n\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited = [[0 for i in range(n)] for j in range(m)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if board[0][i] == 'O':\n",
    "                dfs(0, i, board, visited, 0)\n",
    "\n",
    "        for i in range(n):\n",
    "            if board[m - 1][i] == 'O':\n",
    "                dfs(m - 1, i, board, visited, 0)\n",
    "\n",
    "        for i in range(m):\n",
    "            if board[i][0] == 'O':\n",
    "                dfs(i, 0, board, visited, 0)\n",
    "\n",
    "        for i in range(m):\n",
    "            if board[i][n - 1] == 'O':\n",
    "                dfs(i, n - 1, board, visited, 0)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O' and visited[i][j] == 0:\n",
    "                    dfs(i, j, board, visited, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        if len(board)==0 or len(board[0])==0:\n",
    "            return \n",
    "        \n",
    "        m,n=len(board),len(board[0])\n",
    "        #board_visited=[[ False for i in range(n)] for j in range(m)] \n",
    "        non_flip=[]\n",
    "\n",
    "        directions=[-1,0,1,0,-1]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if board[r][c]=='O':\n",
    "                    self.flip=True\n",
    "                    region=[(r,c)]\n",
    "                    self.__dfs(board,r,c,region,m,n,directions)\n",
    "                    #print(flip)\n",
    "                    if not self.flip:\n",
    "                        non_flip.append(region)\n",
    "        \n",
    "        #print(non_flip)\n",
    "        for region in non_flip:\n",
    "            for r,c in region:\n",
    "                board[r][c]='O'\n",
    "        \n",
    "\n",
    "    def __dfs(self, board: List[List[str]], r: int, c: int, region, m,n,directions)->None:\n",
    "        if r<0 or r>=m or c<0 or c>=n:\n",
    "            return \n",
    "        #global flip\n",
    "        if board[r][c]=='O':\n",
    "            if r==0 or r==m-1 or c==0 or c==n-1:\n",
    "                self.flip=False\n",
    "\n",
    "            region.append((r,c))\n",
    "            board[r][c]='X'\n",
    "            for d in range(4):\n",
    "                self.__dfs(board,r+directions[d],c+directions[d+1],region,m,n,directions) \n",
    "            \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 沉没函数\n",
    "        def dfs1(x,y):\n",
    "            if x<0 or y<0 or x>=len(board) or y>=len(board[0]) or board[x][y]=='X' or  board[x][y]=='B':\n",
    "                return\n",
    "            board[x][y]='B'\n",
    "            dfs1(x,y+1)\n",
    "            dfs1(x+1,y)\n",
    "            dfs1(x-1,y)\n",
    "            dfs1(x,y-1)\n",
    "        def dfs2(x,y):\n",
    "            if x<0 or y<0 or x>=len(board) or y>=len(board[0]) or board[x][y]=='X' or board[x][y]=='O':\n",
    "                return\n",
    "            board[x][y]='O'\n",
    "            dfs2(x,y+1)\n",
    "            dfs2(x+1,y)\n",
    "            dfs2(x-1,y)\n",
    "            dfs2(x,y-1)\n",
    "\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=len(board) or y>=len(board[0]) or board[x][y]=='X' or board[x][y]=='B':\n",
    "                return\n",
    "            board[x][y]='X'\n",
    "            dfs(x,y+1)\n",
    "            dfs(x+1,y)\n",
    "            dfs(x-1,y)\n",
    "            dfs(x,y-1)\n",
    "        for i in range(0,len(board)):\n",
    "            dfs1(i,0)\n",
    "            dfs1(i,len(board[0])-1)\n",
    "        for j in range(1,len(board[0])-1):\n",
    "            dfs1(0,j)\n",
    "            dfs1(len(board)-1,j)\n",
    "        for i in range(1,len(board)-1):\n",
    "            for j in range(1,len(board[0])-1):\n",
    "                dfs(i,j)\n",
    "        for i in range(0,len(board)):\n",
    "            dfs2(i,0)\n",
    "            dfs2(i,len(board[0])-1)\n",
    "        for j in range(1,len(board[0])-1):\n",
    "            dfs2(0,j)\n",
    "            dfs2(len(board)-1,j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        def dfs(i, j, target, flag):\n",
    "            if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == target:\n",
    "                board[i][j] = flag\n",
    "                dfs(i+1, j, target, flag)\n",
    "                dfs(i-1, j, target, flag)\n",
    "                dfs(i, j+1, target, flag)\n",
    "                dfs(i, j-1, target, flag)\n",
    "                \n",
    "        for i in range(len(board)):\n",
    "            dfs(i, 0, 'O', '1')\n",
    "            dfs(i, len(board[0])-1, 'O', '1')\n",
    "        for j in range(len(board)):\n",
    "            dfs(0, j, 'O', '1')\n",
    "            dfs(len(board)-1, j, 'O', '1')\n",
    "        for i in range(1, len(board)-1):\n",
    "            for j in range(1, len(board[0])-1):\n",
    "                dfs(i, j, 'O', 'X')\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == '1':\n",
    "                    board[i][j] = 'O'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs_judge(i, j):    \n",
    "            if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]): return True\n",
    "            if board[i][j] != 'O': return False\n",
    "            board[i][j] = 2\n",
    "            res1 = dfs_judge(i,j-1)\n",
    "            res2 = dfs_judge(i,j+1)\n",
    "            res3 = dfs_judge(i-1,j)\n",
    "            res4 = dfs_judge(i+1,j)\n",
    "            return res1 or res2 or res3 or res4\n",
    "        def dfs_change(i,j, filler):\n",
    "            if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]): return\n",
    "            if board[i][j] != 2: return\n",
    "            board[i][j] = filler\n",
    "            dfs_change(i,j-1, filler)\n",
    "            dfs_change(i,j+1, filler)\n",
    "            dfs_change(i-1,j, filler)\n",
    "            dfs_change(i+1,j, filler)\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 'O':\n",
    "                    if dfs_judge(i, j):\n",
    "                        dfs_change(i, j, 'O')\n",
    "                    else:\n",
    "                        dfs_change(i, j, 'X')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def findX(board, row, col, target):\n",
    "            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] in [\"1\", \"X\"]:\n",
    "                return\n",
    "            if board[row][col] == \"O\":\n",
    "                board[row][col] = target\n",
    "                findX(board, row+1, col, target)\n",
    "                findX(board, row-1, col, target)\n",
    "                findX(board, row, col+1, target)\n",
    "                findX(board, row, col-1, target)\n",
    "        row_num = len(board)\n",
    "        col_num = len(board[0])\n",
    "        for i in range(col_num):\n",
    "            if board[0][i] == \"O\":\n",
    "                findX(board, 0, i, \"1\")\n",
    "            if board[row_num - 1][i] == \"O\":\n",
    "                findX(board, row_num - 1, i, \"1\")\n",
    "        for j in range(row_num):\n",
    "            if board[j][0] == \"O\":\n",
    "                findX(board, j, 0, \"1\")\n",
    "            if board[j][col_num - 1] == \"O\":\n",
    "                findX(board, j, col_num - 1, \"1\")\n",
    "        for i in range(1, row_num-1):\n",
    "            for j in range(1, col_num-1):\n",
    "                if board[i][j] == \"O\":\n",
    "                    findX(board, i, j, \"X\")\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                if board[i][j] == \"1\":\n",
    "                    board[i][j] = \"O\"\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(i, j, label):\n",
    "            if i < 0 or j < 0 or i == len(board) or j == len(board[0]) or board[i][j] != 'O':\n",
    "                return\n",
    "            board[i][j] = label\n",
    "            dfs(i+1, j, label)\n",
    "            dfs(i-1, j, label)\n",
    "            dfs(i, j-1, label)\n",
    "            dfs(i, j+1, label)\n",
    "        \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if i == 0 or j == 0 or i == len(board)-1 or j == len(board[0])-1:\n",
    "                    if board[i][j] == 'O':\n",
    "                        dfs(i, j, 'A')\n",
    "        \n",
    "        for i in range(1, len(board)-1):\n",
    "            for j in range(1, len(board[0])-1):\n",
    "                dfs(i, j, 'X')\n",
    "        \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                board[i][j] = 'O' if board[i][j] == 'A' else 'X'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(board, r, c, flag):  # 统计每个岛屿的面积\n",
    "            if not board or r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or board[r][c] != \"O\":\n",
    "                return\n",
    "\n",
    "            board[r][c] = flag\n",
    "\n",
    "            dfs(board, r + 1, c, flag)\n",
    "            dfs(board, r - 1, c, flag)\n",
    "            dfs(board, r, c + 1, flag)\n",
    "            dfs(board, r, c - 1, flag)\n",
    "\n",
    "\n",
    "        if not board or not board[0]:  # 为空\n",
    "            return\n",
    "\n",
    "        for j in range(len(board[0])):\n",
    "            if board[0][j]==\"O\":\n",
    "                dfs(board,0,j,\"N\")\n",
    "            if board[len(board)-1][j]==\"O\":\n",
    "                dfs(board,len(board)-1,j,\"N\")\n",
    "\n",
    "        for i in range(1,len(board)-1):\n",
    "            if board[i][0]==\"O\":\n",
    "                dfs(board,i,0,\"N\")\n",
    "            if board[i][len(board[0])-1]==\"O\":\n",
    "                dfs(board,i,len(board[0])-1,\"N\")\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == \"O\":\n",
    "                    dfs(board,i,j,\"X\")\n",
    "                if board[i][j] == \"N\":\n",
    "                    board[i][j]=\"O\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(i,j,filpWord,target=\"O\"):\n",
    "            if i<0 or i>=len(board) or j<0 or j>=len(board[0]):\n",
    "                return\n",
    "            if board[i][j]==target:\n",
    "                board[i][j]=filpWord\n",
    "                dfs(i,j-1,filpWord)\n",
    "                dfs(i-1,j,filpWord)\n",
    "                dfs(i+1,j,filpWord)\n",
    "                dfs(i,j+1,filpWord)\n",
    "        i_len = len(board)\n",
    "        j_len = len(board[0])\n",
    "        for i in range(i_len):\n",
    "            if board[i][0]=='O':\n",
    "                dfs(i,0,'A')\n",
    "            if board[i][j_len-1]=='O':\n",
    "                dfs(i,j_len-1,'A')\n",
    "        for j in range(j_len):\n",
    "            if board[0][j]=='O':\n",
    "                dfs(0,j,'A')\n",
    "            if board[i_len-1][j]=='O':\n",
    "                dfs(i_len-1,j,'A')\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if board[i][j]=='O':\n",
    "                    dfs(i,j,'X')\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if board[i][j]=='A':\n",
    "                    board[i][j]='O'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 解法1 岛屿问题(dfs)  淹没封闭岛屿\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        # 处理四周的岛屿 和 封闭岛屿\n",
    "        def dfs(board, i, j, c):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return\n",
    "            if board[i][j] == 'X' or board[i][j] == c:\n",
    "                return\n",
    "            board[i][j] = c\n",
    "            dfs(board, i - 1, j, c)\n",
    "            dfs(board, i + 1, j, c)\n",
    "            dfs(board, i, j - 1, c)\n",
    "            dfs(board, i, j + 1, c)\n",
    "\n",
    "        for i in range(m):\n",
    "            if board[i][0] == 'O':\n",
    "                dfs(board, i, 0, '#')\n",
    "            if board[i][n-1] == 'O':\n",
    "                dfs(board, i, n-1, '#')\n",
    "\n",
    "        for i in range(n):\n",
    "            if board[0][i] == 'O':\n",
    "                dfs(board, 0, i, '#')\n",
    "            if board[m-1][i] == 'O':\n",
    "                dfs(board, m-1, i, '#')\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    dfs(board, i, j, 'X')\n",
    "\n",
    "        # 恢复周围\n",
    "        for i in range(m):\n",
    "            if board[i][0] == '#':\n",
    "                dfs(board, i, 0, 'O')\n",
    "            if board[i][n-1] == '#':\n",
    "                dfs(board, i, n-1, 'O')\n",
    "\n",
    "        for i in range(n):\n",
    "            if board[0][i] == '#':\n",
    "                dfs(board, 0, i, 'O')\n",
    "            if board[m-1][i] == '#':\n",
    "                dfs(board, m-1, i, 'O')\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        track_pos = []\n",
    "        m, n = len(board), len(board[0])\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n: return False \n",
    "            if board[x][y] == \"X\": return True \n",
    "            board[x][y] = \"X\"\n",
    "            track_pos.append([x, y])\n",
    "            if dfs(x-1, y) and dfs(x+1, y) and dfs(x, y-1) and dfs(x, y+1): return True \n",
    "            else: return False \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"O\":\n",
    "                    if not dfs(i, j):\n",
    "                        for pos in track_pos:\n",
    "                            x, y = pos[0], pos[1]\n",
    "                            board[x][y] = \"O\"\n",
    "                    track_pos.clear()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def solve(self, board: List[List[str]]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify board in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        def dfs(board, i, j):\r\n",
    "            if (i == 0 or i == len(board)-1 or j == 0 or j == len(board[0])-1) and board[i][j] == 'O':\r\n",
    "                return False\r\n",
    "            if board[i][j] != 'O':\r\n",
    "                return True\r\n",
    "            board[i][j] = 'T'\r\n",
    "            a = dfs(board, i-1, j)\r\n",
    "            b = dfs(board, i+1, j)\r\n",
    "            c = dfs(board, i, j-1)\r\n",
    "            d =  dfs(board, i, j+1)\r\n",
    "            final_flag = a and b and c and d\r\n",
    "            return final_flag\r\n",
    "        def set_dfs(board, i, j, c):\r\n",
    "            if i > 0 and i < len(board)-1 and j > 0 and j < len(board[0])-1 and board[i][j] == 'T':\r\n",
    "                board[i][j] = c\r\n",
    "                set_dfs(board, i-1, j, c)\r\n",
    "                set_dfs(board, i+1, j, c)\r\n",
    "                set_dfs(board, i, j-1, c)\r\n",
    "                set_dfs(board, i, j+1, c)\r\n",
    "                \r\n",
    "        for i in range(1, len(board)-1):\r\n",
    "            for j in range(1, len(board[0])-1):\r\n",
    "                if board[i][j] == 'O':\r\n",
    "                    if dfs(board, i, j):\r\n",
    "                        set_dfs(board, i, j, 'S')\r\n",
    "                    else :\r\n",
    "                        set_dfs(board, i, j, 'B')\r\n",
    "        for i in range(1, len(board)-1):\r\n",
    "            for j in range(1, len(board[0])-1):\r\n",
    "                if board[i][j] == 'S':\r\n",
    "                    board[i][j] = 'X'\r\n",
    "                elif board[i][j] == 'B':\r\n",
    "                    board[i][j] = 'O'\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
